主页 / 问题 / 1453183
Accepted
Kerian
Asked:2022-10-01 21:21:33 +0000 UTC2022-10-01 21:21:33 +0000 UTC

打印顶点所属的连通分量的编号

  • 772

该程序没有通过测试...在输出文件的第一行打印连接组件的数量。然后打印 N 个整数，其中第 i 个指定第 i 个顶点的连通分量的数量。组件应使用从 1 开始的连续整数编号。组件的编号顺序是任意的。

输入格式：

4 2

12

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 = " ")
графы

1 个回答

  1. Best Answer

    因为组件包含的顶点是按遍历顺序排列的，而不是按编号顺序排列的。例如，如果你输入4 2 3 1 4 2，那么你会得到1 1 2 2，但它应该是1 2 1 2

    如何解决它，你知道吗？

    在我看来，将当前答案写入每个顶点的长度为 n 的列表中更容易，并且根本不需要组件。

    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 = " ")
    • 0

相关问题