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

题目描述

原题链接：105. 有向图的完全联通

代码实现

import collectionsn, k = list(map(int, input().split()))
adjacency = collections.defaultdict(list)
for _ in range(k):head, tail = list(map(int, input().split()))adjacency[head].append(tail)visited_node = set()def bfs(root, adjacency):global visited_nodedeque = collections.deque()deque.append(root)# 每次从队列中取出一个节点，查看邻接表中邻接的节点加入其中，进行BFSwhile deque:node = deque.popleft()visited_node.add(node)		# 遍历过该节点则记录，最后看N个节点是否能被遍历完for tail in adjacency[node]:deque.append(tail)del adjacency[node]return # 使用BFS从1开始遍历，如果所有节点可以被遍历完，则说明完全联通
bfs(1, adjacency)
if len(visited_node) == n:print(1)
else:print(-1)

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