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] = 1result = []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())returnfor 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 defaultdictdef 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())returnfor i in graph[x]:# if graph[x][i] == 1:path.append(i)dfs(graph, i, n, path, result)path.pop()if __name__ == "__main__":main()
