代码随想录算法训练营 Day 43
Published:
图论中的概念
度
无向图中每个节点所连接的边的数量，而有向图中还可分为出度和入度
出度：以该节点作为起始节点的路径数量 入度：以该节点作为终止节点的路径数量
连通性
无向图中任意两个节点之间都有一条路径可达，则称之为连通图
有向图中任意两个节点之间都有一条路径可刀，则称之为强连通图
（强）连通分量
一个极大的（强）连通子图被称为一个（强）连通分量
Q1. KamaCoder 98
from collections import defaultdict
res = []
def dfs(node, path):
if node == n:
res.append(path[:])
return
for neigh in edge[node]:
if neigh in path:
continue
path.append(neigh)
dfs(neigh, path)
path.pop()
if __name__ == '__main__':
n, m = map(int, input().split())
edge = defaultdict(list)
for _ in range(m):
n1, n2 = map(int, input().split())
edge[n1].append(n2)
dfs(1, [1])
if not res:
print(-1)
for p in res:
print(' '.join(map(str, p)))
广度优先搜索
适合于找最短路径类似的问题