Leetcode 刷题笔记1 图论part01
图论的基础知识：
图的种类： 有向图（边有方向） 、 无向图（边无方向）、加权有向图（边有方向和权值）
度： 无向图中几条边连接该节点，该节点就有几度；有向图中每个节点有入度和出度
连通性：在无向图中，任何两个节点都是可以到达的，称之为连通图，否则称之为非连通图
在有向图中，热河两个节点是可以相互到达的，称之为强连通图
联通分量：在无向图中的极大连通子图称之为该图的一个连通分量
强连通分量：有向图中极大强连通子图称之为强连通分量
图的构造：一般使用邻接表、邻接矩阵和朴素存储
图的遍历方式：深度优先搜索（dfs）、广度优先搜索（bfs）
卡码网 98 所有可达路径
import sys
from collections import defaultdict
path = []
result = []
def main():
n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
x, t = map(int, input().split())
graph[x].append(t)
path.append(1)
dfs(graph, 1, n)
if not result:
print(-1)
for pa in result:
print(' '.join(map(str, pa)))
def dfs(graph, x, n):
if x == n:
result.append(path.copy())
return
for i in graph[x]:
path.append(i)
dfs(graph, i, n)
path.pop()
if __name__ == '__main__':
main()