day_50
98. 所有可达路径
def dfs(graph, x, n, path, res):if x == n:res.append(path.copy())returnfor i in range(1, n + 1):if graph[x][i] == 1:path.append(i)dfs(graph, i, n, path, res)path.pop()def main():n, m = map(int, input().split())graph = [[0] * (n + 1) for _ in range(n + 1)]for _ in range(m):s, t = map(int, input().split())graph[s][t] = 1 res = []dfs(graph, 1, n, [1], res)if not res:print(-1)else:for path in res:print(' '.join(map(str, path)))if __name__ == '__main__':main()
邻接表方式
from collections import defaultdictdef dfs(graph, x, n, path, res):if x == n:res.append(path.copy())returnfor i in graph[x]:path.append(i)dfs(graph, i, n, path, res)path.pop()def main():n, m = map(int, input().split())graph =defaultdict(list)for _ in range(m):s, t = map(int, input().split())graph[s].append(t)res = []dfs(graph, 1, n, [1], res)if not res:print(-1)else:for path in res:print(' '.join(map(str, path)))if __name__ == '__main__':main()
就一深搜，虽然我不能自己写出来，但是这个不难。
邻接表和邻接矩阵都只是存储图的一种方式，在存储和遍历的时候有所不同，解题思路都是一样的。