强连通分量和 Tarjan
强连通分量(Strongly Connected Components，SCC)，指的是极大的连通子图。
tarjan 算法，用于求图的强连通分量。
dfs 生成树
有向图的 dfs 生成树大致分为四种边：
- 树边(tree edge)：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边(back edge)：示意图中以红色边表示(即 \(7 \rightarrow 1\))，也被叫做回边，即指向祖先结点的边。
- 横叉边(cross edge)：示意图中以蓝色边表示(即 \(9 \rightarrow 7\))，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
- 前向边(forward edge)：示意图中以绿色边表示（即 \(3 \rightarrow 6\))，它是在搜索的时候遇到子树中的结点的时候形成的。
如果结点 \(u\) 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 \(u\) 为根的子树中。结点 \(u\) 被称为这个强连通分量的根。
反证法：假设有个结点 \(v\) 在该强连通分量中但是不在以 \(u\) 为根的子树中，那么 \(u\) 到 
的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 \(u\) 是第一个访问的结点矛盾了。得证。
Tarjan 求强连通分量
需要对每个节点 \(u\) 都维护以下几个信息：
- \(dfn_u\)：\(u\) 在深度优先搜索时是第几个被访问的
(人称豆腐脑序)。 - \(low_u\)：在 \(u\) 的子树中能够回溯到的最早的在栈中的结点。
很明显，对于每个 \(u\) 的后代 \(i\) 都有 \(dfn_u < dfn_i\)。从根开始的一条路径上的 \(dfn\) 严格递增，\(low\) 严格非降。
用 dfs 来求 \(dfn\) 和 \(low\)，每搜索到一个新的节点就让它入栈，每找到一个强连通分类，就让它们出栈。
当节点 \(u\) 向节点 \(v\) 做遍历时，有三种情况：
- \(v\) 未被访问，则对 \(v\) 进行 dfs，回溯时
low[u] = min(low[u], low[v]);因为存在从 \(u\) 到 \(v\) 的直接路径，所以 \(v\) 能够回溯到的已经在栈中的结点，\(u\) 也一定能够回溯到。 - \(v\) 已被访问且仍在栈中，那么
low[u] = min(low[u], dfn[v]); - \(v\) 被访问过且已不在栈中，说明 \(v\) 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
处理完以后，我们可以想到在一个强连通分量里有且仅有一个点 \(u\) 满足 \(dfn_u=low_u\)，该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 \(dfn\) 和 \(low\) 值最小，不会被该连通分量中的其他结点所影响。
所以只要在回溯的过程中判断 \(dfn_u\) 是否和 \(low_u\) 相等，若相等，则栈内 \(u\) 及它上方的节点构成一个 SCC。
const int N = 1e4 + 10;
int n, dfncnt, dfn[N], low[N], bel[N], stk[N], top, fstk[N], sc, sz[N], b[N], ans, sum, c[N];
vector<int> g[N];
void tarjan (int x) {
dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
for (int i : g[x]) {
if (!dfn[i]) {
tarjan(i), low[x] = min(low[x], low[i]);
} else if (fstk[i]) {
low[x] = min(low[x], dfn[i]);
}
}
if (dfn[x] == low[x]) {
++sc;
while (1) {
sz[sc]++, fstk[stk[top]] = 0, bel[stk[top--]] = sc;
if (stk[top + 1] == x) {
break;
}
}
}
}
应用
我们可以将每个强连通分量都压缩成一个点(缩点)，那么原图就会变成 DAG，可以进行拓扑排序等。
例题
P2746 [USACO5.3] 校园网Network of Schools | #10091. 「一本通 3.5 例 1」受欢迎的牛
割点和割边
割点
对于一个无向图，如果把这个点删除后这个图的极大连通分量数增加了，那么这个点就是原图的割点(割顶)。
举个例子，这张图内的割点明显只有 \(2\)。
首先我们先通过 DFS 给它们打上时间戳：
记录在 \(dfn\) 中，还需要另外一个数组 low，用它来存储不经过其父亲能到达的最小的时间戳。
好，和 Tarjan 扯上关系了，那么首先 Tarjan 预处理一下，可以得到定理：对于某个顶点 \(u\)，如果存在至少一个顶点 \(v\)(\(u\) 的儿子)，使得 \(low_v \geqslant dfn_u\)，即不能回到祖先，那么 \(u\) 点为割点。
但是对于搜索树的根节点需要特殊处理：若该点不是割点，则其他路径亦能到达全部结点，因此从起始点只「向下搜了一次」，即在搜索树内仅有一个子结点。如果在搜索树内有两个及以上的儿子，那么他一定是割点了(设想上图从 \(2\) 开始搜索，搜索树内应有两个子结点：\(3\) 或 \(4\) 及 \(5\) 或 \(6\))。如果只有一个儿子，那么把它删掉，不会有任何的影响。比如下面这个图，此处形成了一个环。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int n, m, dfncnt, dfn[N], low[N], bel[N], stk[N], top, fstk[N], sc, sz[N], cnt;
vector<int> g[N];
bool ans[N];
void tarjan (int x, int fa) {
int son = 0;
dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
for (int i : g[x]) {
if (!dfn[i]) {
son++;
tarjan(i, x), low[x] = min(low[x], low[i]);
if (fa != x && low[i] >= dfn[x] && !ans[x]) {
ans[x] = 1, cnt++;
}
} else if (i != fa) {
low[x] = min(low[x], dfn[i]);
}
}
if (fa == x && son >= 2 && !ans[x]) {
ans[x] = 1, cnt++;
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
dfncnt = 0, tarjan(i, i);
}
}
cout << cnt << '\n';
for (int i = 1; i <= n; i++) {
if (ans[i]) {
cout << i << ' ';
}
}
return 0;
}
割边
对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图 \(G=\{V,E\}\)，\(e\) 是其中一条边(即 \(e \in E\))，如果 \(G-e\) 是不连通的，则边 \(e\) 是图 \(G\) 的一条割边(桥)。
比如下图中红色边就是割边。
和割点差不多，不需要特殊考虑更根节点，只要把 \(low_v \geqslant dfn_u\) 改为 \(low_v > dfn_u\) 即可。
void tarjan (int x, int fa) {
int son = 0;
dfn[x] = low[x] = ++dfncnt, fstk[x] = 1, stk[++top] = x;
for (int i : g[x]) {
if (!dfn[i]) {
son++;
tarjan(i, x), low[x] = min(low[x], low[i]);
if (low[i] > dfn[x] && !ans[x]) {
ans[x] = 1, cnt++;
}
} else if (i != fa) {
low[x] = min(low[x], dfn[i]);
}
}
}