day50 第十一章：图论part01
ACM模式，自己控制输入输出
图论理论基础
连通性：
连通图（无向），强连通图（有向）----- 任意两个节点之间都可相互到达
连通分量（极大连通子图），强连通分量
图的构造：
邻接矩阵
优点：
表达简单
易于查找任意2个顶点之间的连接
适合稠密图
缺点：
n*n，不适合稀疏图
邻接表
优点：
空间利用率高
缺点：
不好搜索任意2点之间是否存在
回溯就是深度优先搜索
邻接表和邻接矩阵dfs写法上没有太大差异
深搜理论基础
98. 所有可达路径
邻接矩阵：n*n的矩阵
def main():
n, m = map(int, input().split())
graph = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
s, t = map(int, input().split())
graph[s][t] = 1
result = []
path = [1]
dfs(graph, 1, n, path, result)
if not result:
print(-1)
else:
for path in result:
print(' '.join(map(str, path)))
def dfs(graph, x, n, path, result):
if x==n:
result.append(path.copy())
return
for i in range(1, n+1):
if graph[x][i] == 1:
path.append(i)
dfs(graph, i, n, path, result)
path.pop()
if __name__ == "__main__":
main()邻接表：defaultdict
from collections import defaultdict
def main():
n, m = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
s, t = map(int, input().split())
graph[s].append(t)
result = []
path = [1]
dfs(graph, 1, n, path, result)
if not result:
print(-1)
else:
for path in result:
print(' '.join(map(str, path)))
def dfs(graph, x, n, path, result):
if x == n:
result.append(path.copy())
return
for i in graph[x]:
# if graph[x][i] == 1:
path.append(i)
dfs(graph, i, n, path, result)
path.pop()
if __name__ == "__main__":
main()