Вывести номер компоненты связности, к которой принадлежит вершина

Question

Программа не проходит тесты... В первой строчке выходного файла выведите количество компонент связности. Далее выведите N целых чисел, i -е из них задаёт номер компоненты связности для i -й вершины. Компоненты следует нумеровать последовательными целыми числами от 1. Порядок нумерации компонент произвольный.

формат ввода:

4 2

1 2

3 4

формат вывода:

2

1 1 2 2

from sys import stdin 
 
input = stdin.readline 
 
n, m = map(int, input().split()) 
 
graph = [[] for _ in range(n)] 
for i in range(m): 
    u, v = [int(i)-1 for i in input().split()] 
    graph[u].append(v) 
    graph[v].append(u) 
 
visited = [False] * n 
answer = 0 
components = [] 
 
for i in range(n): 
    if visited[i]: 
        continue 
 
    answer+=1 
    visited[i] = True 
    queue = [i] 
    component = [] 
    while queue: 
        v = queue.pop() 
        component.append(v+1) 
        for to in graph[v]: 
            if not visited[to]: 
                visited[to] = True 
                queue.append(to) 
    components.append(component) 
 
print(answer)
l =0
for i in range(answer):
    l+=1
    for k in range (len(components[i])):
        print(l, end = " ")

Answer 1

Потому что в components лежат вершины в порядке обхода, а не в порядке нумерации. Например, если ввести 4 2 3 1 4 2, то получится 1 1 2 2, а должно быть 1 2 1 2

Как поправить, разберётесь?

На мой взгляд, проще в один список длиной n для каждой вершины записывать текущий answer, а components совсем не нужны.

co = [0] * n
...
visited[i] = True
co[i] = answer
     ...
            visited[to] = True
            co[to] = answer    

print(answer)
for i in range(n):
    print(co[i], end = " ")

БЛОГ НА HUSL

Вывести номер компоненты связности, к которой принадлежит вершина

Ответы (1 шт):