强连通分量
连通性的定义
-
无向图：
- 连通：任意两点之间都可达。
- 点双连通：任意删去一点之后任意两点之间还可达。
- 边双连通：任意删去一边之后任意两点之间还可达。
-
有向图：
- 弱连通：一个有向图把边替换成无向边后可以得到一张连通图。
- 强连通：一个有向图在有向情况下就是一张连通图。
强连通分量
从原图中选出一些节点和一些边构成的图，叫做这个原图的子图。
而如果该子图为连通图，则这个子图被称为连通子图。
一个连通子图的节点数和边数都极大，则成它为极大连通子图。
极大强连通子图被称为强连通分量，即 Strongly Connected Components，简称为 SCC。
DFS 树
DFS 树，又称为 DFS 生成树、DFS 搜索树，为遍历一张图的过程中，第一次到达每个点的每条边组成的树，根节点不算。
下图就是一张 DFS 树的示例图：
在有向图中，与 DFS 树有关的有四类边：
- 树边（上图中黑色实线），从父节点指向还没有被访问的子节点。
- 反祖边（上图中红色虚线），从子孙节点指向祖先节点的边。
- 前向边（上图中绿色虚线），指向子树中的边。
- 横叉边（上图中蓝色虚线），指向已经访问过但既不是祖先节点也不是子树中的边。
注意，前向边和横叉边只在有向图的 DFS 树中存在，无向图中只有树边和返祖边。
强连通分量求解结论
DFS 树和强连通分量的关系有一条结论：对于一个 SCC 中最先被搜到的点 \(u\)，这个 SCC 中剩余的其他节点一定都在以 \(u\) 为根的子树中。
证明：
采用反证法。
对于这个 SCC 中的点 \(v\)，假设点 \(v\) 不在以 \(u\) 为根的子树中。那么 \(u\) 到 \(v\) 的路径上一定有不包含在这个子树内的边，即横叉边或返祖边。这都要求指向的节点已经被访问过。
因为 \(u\) 和 \(v\) 在同一个 SCC 中，那么访问这些更早被访问的点时肯定能访问到 \(u\)，这和 \(u\) 是最先被搜到的矛盾。
得证。
实现
具体实现时，为了能快速取到被访问过节点的信息，我们采用栈（即 stack）存储所有被访问过的节点编号，找 SCC 时就取出连续一段来。
void Tarjan(int u){f[u]=(++cnt),id[u]=f[u];st.push(u),vis[u]=1;for(int v:g[u])if(!id[v])Tarjan(v),f[u]=min(f[u],f[v]);else if(vis[v])f[u]=min(f[u],id[v]);if(f[u]==id[u]){vector<int> tmp;tmp.clear();while(tmp.empty()||tmp.back()!=u)vis[st.top()]=0,tmp.pb(st.top()),st.pop();SCCs[++tot]=tmp;}return;
}