213、【图论】有向图的完全联通（Python）

题目描述

原题链接：105. 有向图的完全联通
代码实现

1. import collections
3. n, k = list(map(int, input().split()))
4. adjacency = collections.defaultdict(list)
5. for _ in range(k):
6.     head, tail = list(map(int, input().split()))
7.     adjacency[head].append(tail)
9. visited_node = set()
11. def bfs(root, adjacency):
12.     global visited_node
14.     deque = collections.deque()
15.     deque.append(root)
17.         # 每次从队列中取出一个节点，查看邻接表中邻接的节点加入其中，进行BFS
18.     while deque:
19.         node = deque.popleft()
20.         visited_node.add(node)                # 遍历过该节点则记录，最后看N个节点是否能被遍历完
22.         for tail in adjacency[node]:
23.             deque.append(tail)
25.         del adjacency[node]
26.    
27.     return
29. # 使用BFS从1开始遍历，如果所有节点可以被遍历完，则说明完全联通
30. bfs(1, adjacency)
31. if len(visited_node) == n:
32.     print(1)
33. else:
34.     print(-1)

复制代码

参考文章：105.有向图的完全可达性

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。