图论

最短/最长路径计算方法

其中$w$指边的权重

图的类型	最短路径	最长路径
DAG ($w \in \mathbb{R}$)	DP(Toposort)	DP(Toposort)
一般有向/无向图	$w = \text{const}$: BST $w \in \mathbb{R}^+$: Dijkstra $w \in \mathbb{R}$: Bellman-Ford	NP-hard(具体证明)

环的检测

图的类型	方法
无向图	UF：动态方法 DFS：遍历
有向图	BFS：拓扑排序 DFS：染色法

连通分量计算方法（未完成）

图的类型	连通分量	计算方法
无向图		UF：动态方法 DFS：遍历
有向图	SCC（强连通分量）	Toposort+DFS （计算后的SCC是一个DAG）