跳转至

SCC

定义

连通:两个节点之间有路径相连,那么两点是连通的。

强连通:如果有向图 \(G\) 中任意两点是连通的,那么 \(G\) 是强连通的。

连通分量:有向图图 \(H\)\(G\) 的子图,且 \(H\) 是最大的强连通图,那么 \(H\) 就是 \(G\) 的强连通分量。

Tarjan 算法