Дан неориентированный граф из n вершин и m ребер

@ANDREi_199 · Регистрация: 19.12.2021

Студворк — интернет-сервис помощи студентам

Дан неориентированный граф из n вершин и m ребер. Требуется покрасить каждую вершину в какой-либо цвет от 1 до n, чтобы цвета вершин совпадали тогда и только тогда, когда они друг из друга достижимы.

Входные данные:
В первой строке даны числа n и m (1≤n,m≤1000000). Дальше в m строках перечислены попарно различные пары вершин графа ui,vi, между которыми есть ребро (1≤ui,vi≤n).

Выходные данные:
Выведите n чисел через пробел — i-е число равно цвету i-й вершины.

Примеры:
1) входные данные
3 2
1 2
2 3
выходные данные
1 1 1

2) входные данные
3 1
1 2
выходные данные
1 1 2

@idealist · 18.01.2022, 14:38

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def set_color(b, a):
    if color[b] == b:
        color[b] = a
    elif color[b] < a:
        set_color( a, color[b] )
    else:
        set_color( color[b], a )
        color[b] = a
#==============================================================================
n, m = map(int, ( input('n, m = ').split() ) )
color = [ i for i in range(n) ]
for j in range(m):
    a, b = sorted( map(int, ( input('-> ').split() ) ) )
    set_color(b-1,a-1)
for i in range(n):
    if color[i] != i:
        color[i] = color[ color[i] ]
    print( color[i] + 1, end=' ' )

@ANDREi_199 · 18.01.2022, 16:04 **[ТС]**

это что такое ты щас написал?

@Semen-Semenich · 18.01.2022, 16:06

Не по теме:

Сообщение от ANDREi_199

это что такое ты щас написал?

индийскую мантру

@ANDREi_199 · 18.01.2022, 16:39 **[ТС]**

па русский язык можно?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def set_color(b, a):
    if color[b] == b:
        color[b] = a
    elif color[b] < a:
        set_color( a, color[b] )
    else:
        set_color( color[b], a )
        color[b] = a
#==============================================================================
n, m = map(int, ( input('n, m = ').split() ) )
color = [ i for i in range(n) ]
for j in range(m):
    a, b = sorted( map(int, ( input('-> ').split() ) ) )
    set_color(b-1,a-1)
for i in range(n):
    if color[i] != i:
        color[i] = color[ color[i] ]
    print( color[i] + 1, end=' ' )

@ANDREi_199 · 19.01.2022, 15:32 **[ТС]**

как это решать подскажите!!! надо типа формулу\
color[i] * color[i] = color или чето такое

@Catstail · 19.01.2022, 16:48

Сообщение от ANDREi_199

надо типа формулу

- "типа формула" здесь не при чем. Тебе привели программу решения. А у тебя не хватает соображения это понять.

Вот сайт, где объясняется алгоритм раскраски (с картинками).

Если "не доходит" - займись чем-нибудь другим. Помимо программирования есть много интересных и полезных занятий. А будешь хамить - вылетишь с Форума.

@shinzin · 15.02.2022, 18:42

1qq

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@ANDREi_199 1 / 1 / 0 Регистрация: 19.12.2021 Сообщений: 60

	Дан неориентированный граф из n вершин и m ребер 17.01.2022, 17:08. Показов 5205. Ответов 7 Метки нет (Все метки) Дан неориентированный граф из n вершин и m ребер. Требуется покрасить каждую вершину в какой-либо цвет от 1 до n, чтобы цвета вершин совпадали тогда и только тогда, когда они друг из друга достижимы. Входные данные: В первой строке даны числа n и m (1≤n,m≤1000000). Дальше в m строках перечислены попарно различные пары вершин графа ui,vi, между которыми есть ребро (1≤ui,vi≤n). Выходные данные: Выведите n чисел через пробел — i-е число равно цвету i-й вершины. Примеры: 1) входные данные 3 2 1 2 2 3 выходные данные 1 1 1 2) входные данные 3 1 1 2 выходные данные 1 1 2 0

@ANDREi_199 1 / 1 / 0 Регистрация: 19.12.2021 Сообщений: 60
	18.01.2022, 16:04 [ТС]
	это что такое ты щас написал? 0

@ANDREi_199 1 / 1 / 0 Регистрация: 19.12.2021 Сообщений: 60
	19.01.2022, 15:32 [ТС]
	как это решать подскажите!!! надо типа формулу\ color[i] * color[i] = color или чето такое 0

@shinzin -2 / 6 / 5 Регистрация: 19.01.2022 Сообщений: 201
	15.02.2022, 18:42
	1qq 0