强连通分量 学习笔记
djwj233
2021-07-27 17:11:20
### 1. 有向图中连通性的概念
对于有向图 $G=(V,E)$，若存在一条路径从 $u$ 到 $v$，则称 $u$ **可达** $v$。
特别地，若存在一个点 $u$ 满足从 $u$ 出发能够到达 $V$ 中的所有点，则称 $G$ 为**流图**（*flow graph*），$u$ 被称为 $G$ 的**源点**（*Source*），记为 $(G,u)$。
不难发现，任意有向图都能被分为若干张子图，使每个子图都是流图。
若对任意 $u,v\in V$，都有 $u$ 可达 $v$，则称 $G$ 为**强连通图**（*strongly connected graph*）
而若把 $E$ 中的边全部替换为无向边后得到的无向图（这成为它的**基图**（*base graph*））是连通的，则称 $G$ 为**弱连通图**（*weakly connected graph*）
显然，图 $G$ 弱连通是其强连通的必要不充分条件。
若有强连通图 $F\subseteq G$，且不存在另一个强连通图 $H$ 使 $F\subsetneqq H\subseteq G$，则称 $F$ 是 $G$ 的**强连通分量**（*strongly connected component*，*SCC*）。
同样地我们可以定义**弱连通分量**（*weakly connected component*）。它们也分别被称为**极大强连通子图**和**极大弱连通子图**。
### 2. Tarjan 算法的原理与主过程
*Tarjan* 算法可以在 $\Theta(n)$ 的时间内求出一张图的 *SCC*。
我们对一张流图 $(G,s)$，从 $s$ 出发进行一次 DFS。
记第 $i$ 个点的 DFS 序为 $dfn(i)$，此时流图中的所有边 $(u,v)$ 被分为了四类：
- **树边**（*tree edge*）：这条边在 DFS 时被搜索到了；
- **前向边**（*forward edge*）：此边不是树边，且有 $dfn(u)<dfn(v)$，同时 $u$ 是 $v$ 的祖先；
- **返祖边**（*back edge*）：此边不是树边，且有 $dfn(u)>dfn(v)$，同时 $v$ 是 $u$ 的祖先；
- **横叉边**（*cross edge*）：$u$ 既不是 $v$ 的祖先，也不是 $v$ 的后代。
我们发现，**一个环一定是强连通图**。那么，我们只需要**对每个结点，找出所有和它构成一个环的点**。
那么，我们发现返祖边能和树边一起构成一个环，一些横叉边能和返祖边、树边构成一个环。
因此，我们要**维护一个栈**，保存以下的两种点：
- $x$ 的所有祖先，记为 $anc(x)$。（*ancestors*）
- 所有已搜过的、能到达 $anc(x)$ 的点。
我们定义一个**追溯值** $low(i)$，表示从 $subtree_i$ 出发所能到达的**最早的 $dfn$ 值**。
容易知道，对 $x$ 的所有后代 $y$，均有 $low(x)\leq low(y)$。
*Tarjan* 算法的主过程 $\texttt{tarjan(x)}$ 如下：
1. 记录 $dfn(x)$ 的值，先赋值 $low(x)$ 为 $dfn(x)$，将 $x$ 入栈。
2. 枚举每条从 $x$ 出发的点 $(x,y)$。
3. 若 $y$ 未被访问过，那么 $(x,y)$ 为树边。执行 $\texttt{tarjan(y)}$，用 $low(y)$ 去更新 $low(x)$。
4. 若 $y$ 已经被访问过且 $y$ 在栈中，那么用 $low(y)$ 去更新 $low(x)$。（其实这里用 $low(y)$ 和用 $dfn(y)$ 是一样的，证明略去）
5. 若回溯时有 $dfn(x)=low(x)$ 成立，则弹出栈中的所有元素直至 $x$ 出栈。弹出的所有元素构成一个 *SCC*。
设点集为 $S$，证明算法的正确性：
- 由于点集中除了 $x$ 以外的点 $y$ 都满足 $low(y)<dfn(y)$，也就是说从 $y$ 出发能到达比 $y$ 时间戳早的结点，那么简单归纳可得：
**点集中的所有点都能到达 $x$。**
又因为点集 $S\subseteq subtree(x)$，那么对任意点对 $(u,v)$，我们都可以构造一条从 $u$ 到 $x$，从 $x$ 再到 $v$ 的路径。可知它一定是强连通图。
这便证明了其**强连通性**。
- 因为此时 $dfn(x)=low(x)$，那么从 $subtree(x)$ 出发**已经不能达到其它的子树外的点**。
这说明这个强连通图**不可能再扩张**形成更大的强连通图。这便证明了其**极大性**。
- 综上，弹出的所有点构成一个 *SCC*，归纳可得此算法的正确性。
容易说明这个算法是 $\Theta(n+m)$ 的。
求出所有的 *SCC* 后，我们把每个 *SCC* 当作一个点看待，重新连边。易知这样图就变成了一张**有向无环图**，那么就可以简化问题了。
这个过程叫做**缩点**，是 *Tarjan* 算法在 OI 中的一个重要用途。
**一般地，若一个问题可以在 *DAG* 上得到求解，那么可以考虑通过缩点将其推广到普通有向图**。
### 3. Tarjan 的实现与基本应用
- 模板：[B3609 [图论与代数结构 701] 强连通分量](https://www.luogu.com.cn/problem/B3609)
按照上面的做法直接写即可。
```c++
void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
st[++top]=x, ins[x]=true;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
} else if(ins[y])
low[x]=min(low[x],low[y]);
}
if(low[x]==dfn[x]) {
res++;
while(st[top]!=x) {
scc[res].push_back(st[top])；
bel[st[top]]=res, ins[st[top]]=false;
top--;
}
scc[res].push_back(x);
bel[x]=res, ins[x]=false;
top--;
sort(scc[res].begin(),scc[res].end());
}
}
```
主函数中，由于**原图不一定是流图**，所以我们要手动多次 DFS，将原图分为多个流图。
```c++
fo(i,1,n) if(!dfn[i]) tarjan(i);
```
**这是非常重要的！！！**
[Code](https://www.luogu.com.cn/record/54348206)
- [P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G](https://www.luogu.com.cn/problem/P2341)
缩点，然后大力拓扑排序，对每个 *SCC* 都算出有几头牛喜欢这个 *SCC* 中的牛。
这可以用`bitset`在 $\Theta(\frac{nm}{w})$ 内完成。
Data：
```
4 4
1 2
1 3
2 4
3 4
```
[Code](https://www.luogu.com.cn/record/54356503)
- [P3387 【模板】缩点](https://www.luogu.com.cn/problem/P3387)
之所以把这题放后面是因为这题比前一题略难，也不容易找到思路。
不过总之还是思博题，直接在 DAG 上 DP 就完事了。
[Code](https://www.luogu.com.cn/record/54438345)
- [P2812 校园网络【[USACO]Network of Schools加强版】](https://www.luogu.com.cn/problem/P2812)
显然要先缩点然后再做。
那么第一个问题的答案应该是**所有入度为 $0$ 的 *SCC***。因为一方面除了自己，没有任何方式可以传给它；另一方面，由于别的 *SCC* 入度均不为 $0$，那么一定有方法能传递给它们。
第二问稍难一点，结论是**所有入度为 $0$ 的 *SCC* **的数量和**所有出度为 $0$ 的 *SCC* **的数量的较大值。
一方面，我们发现答案至少是这个值。否则总存在一个入度为 $0$ 或出度为 $0$ 的 *SCC* 无法被连到，不符合定义。
另一方面，我们只要让所有的原先入度为 $0$ 的 *SCC* 有至少一条如边，原先出度为 $0$ 的 *SCC* 有至少一条出边便可形成一个 *SCC*。
但是需要特判一种情况，就是原图本身就是 *SCC*，这时答案为 $0$。
[Code](https://www.luogu.com.cn/record/54394721)
### 4. Kosaraju 算法
*Kosaraju* 算法是另一种求解 *SCC* 的做法。
尽管其时间复杂度也是线性的，但是需要建两张图，跑两遍 DFS，常数较大。而且通用性也不如 *Tarjan* 强，一般不使用。
（但还是在这儿记一笔，免得初赛考到）
*Kosaraju* 算法的主过程：
- 对**反图**进行 DFS，按照 DFS 序依次将所有点扔入栈中。
- 对**原图**按照 **从栈顶到栈底的顺序** DFS。一次 DFS 中搜到的所有结点是一个 *SCC*。
容易看出，**其核心在于封死连通分量往外走的路**。
正确性证明可参考[这篇博客](https://blog.csdn.net/u010742342/article/details/70238363)。