强连通分量
_Cheems
·
·
个人记录
基础概念
强连通：一个有向图中，若 u 和 v 可以互相到达，则称 u 和 v 强连通。
强连通图：若有向图 G 中的任意两点强连通，则称 G 是强连通图。
强连通分量：有向图 G 的任意极大强连通子图，称作强连通分量。
补充：极大，顾名思义就是不能再大。若强连通图 G 为强连通图 H 的子图，则 G 一定不是强连通分量。
求强连通分量的意义
任意图都可以分解为若干个强连通分量。
将每个强连通分量缩为一点，则原本复杂的图就被化为一个 DAG，它具有许多优点。
由强连通图的定义得，其中任意两点均可互相到达。因此，设有强连通分量 U、V，若缩点后点 u 可到达点 v ，则 U 中的任意点均可到达 V 中的任意点。
于是遇到一些题目时可以考虑缩点求解。
Tarjan 算法
介绍一种求强连通分量的方法。
定义三个数组记录点 $u$ 信息：
* $dfn[u]$ ：时间戳数组，即访问点 $u$ 的次序。
* $vis[u]$ ：点 $u$ 的状态。$0$ 表示未访问，$1$ 表示访问了但不确定所在强连通分量，$2$ 表示已确认所在强连通分量。
* $low[u]$ ：点 $u$ 可到达点的最小 $dfn$。
像 $DFS$ 一样遍历每个点，并维护上述数组。同时，将点依次加入一个栈中。
关键一步来了，对于点 $u$，当访问完它所有可到点后，易发现： $low$ 值相等的点在同一个强连通分量中，且有且仅有一个点满足 $dfn$ 值与 $low$ 值相等。
最重要的是，栈中这个点以及它上面的所有元素都在同个强连通分量里，只需要弹出记录即可。
为啥捏？
1. 不多：不妨自己画图试试，可发现，第一个（被记录的）强连通分量在栈中呈区间排列。当它弹出后继续遍历直到满足条件，此时，栈中同强连通分量的元素又呈区间排列。以此类推，不会多记录。
2. 不少：由定义易得， $dfn$ 值与 $low$ 值相等得点一定是强连通分量中第一个被遍历的点，因此，不会栈中有别的点（同强连通分量）在其底部。
需要注意横叉边（$v$ 已是强连通分量）啊，否则会胡乱更新 $low$ 值。
代码如下：
```cpp
void Tarjan(int u) {
low[u] = dfn[u] = ++tc;
vis[u] = 1; stk[++top] = u;
for (int v : g[u]) {
if (vis[v] == 2) continue;
if (!vis[v]) Tarjan(v);
low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u]) {
++cnt; int v;
do {
v = stk[top--];
bel[v] = cnt;
vis[v] = 2;
} while (v ^ u);
}
}
```
### 例题
#### 1
洛谷上没有
题意：
给定一个 $n$ 个点，$m$ 条边的有向图，求有多少个点满足所有点都能到达它。
解法：
有向图，考虑缩点。
缩点后得到 $DAG$，其中出度为 $0$ 的点一定能被所有点到达。统计其数量，如果大于 $1$，则答案为 $0$，因为它们间不可互相到达；如果恰好为 $1$，输出该点所包含点的数量即可。
#### 2
[P2746 [USACO5.3] 校园网Network of Schools](https://www.luogu.com.cn/problem/P2746)
解法：
缩点得到 $DAG$。
任务 $A$ ：
很容易，统计缩点后入度为 $0$ 的点的数量即可。
任务 $B$ ：
求至少添加几条边，使得该图变为强连通图，通过构造法求解。
只考虑入度或出度为 $0$ 的点即可。设有 $a$ 个入度为 $0$ 的点，$b$ 个出度为 $0$ 的点。
分情况讨论，当 $a$ 小于等于 $b$ 时，可构造出一种花费为 $b$ 的解法，详细步骤如下（摘自云课堂）。
“ 我们从 $B$ 类点中找出 $a$ 个点，然后和 $A$ 类点一一对应连接，由 $B$ 类点连向 $A$ 类点。（注意：需要确保连接的两点原先是不在一个 $DAG$ 里的。） ”
“ 然后剩下的 $B$ 类点只需要随便连向一个 $A$ 类点即可。这样答案就是 $b$。”
由于花费 $b-1$ 条边只能把 $B$ 类点相连，且 $A$ 类点数量不可能为 $0$。因此花费不能小于 $b$，而我们又得到一种花费 $b$ 的解法，所以此时的答案为 $b$。
同理，$a$ 大于 $b$ 时，答案为 $a$。
整理得：$ans=max(a,b)$。