部分定义摘自 Alex_Wei 的博客，如有侵权，请联系笔者删除。
割点
在无向图中，删去后使得连通分量数增加的结点称为割点。
孤立点不是割点。
非根节点 \(u\) 为割点当且仅当 dfs 树上存在一条树边 \(u \rightarrow v\) 使得 \(\operatorname{low}_v \geq \operatorname{dfn}_u\)。
根节点 \(u\) 为割点当且仅当 dfs 树上 \(u\) 有两个以上的子节点。
void tarjan(int u, int last, bool isRoot) {
dfn[u] = low[u] = ++timer;
int son = 0;
for (int i = head[u]; ~i; i = E[i].nxt) {
if (i == (last ^ 1)) continue;
int v = E[i].v;
if (!dfn[v]) {
son++; tarjan(v, i, false);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && !isRoot) isCut[u] = true;
}
else low[u] = min(low[u], dfn[v]);
}
if (isRoot && son >= 2) isCut[u] = true;
}
点双连通分量
点双连通图：不存在割点的无向连通图称为点双连通图，孤立点和孤立边均为点双连通图。
点双连通分量：一张图的极大点双连通子图称为点双连通分量（V-BCC），简称点双。
性质
- 两个点双至多存在一个公共点（该点一定是割点）。
- 任意一个非割点的点都只存在于一个点双中，割点一定属于两个及以上的点双。
- 对于一个点双（除去孤立边），其内部任意两不同点一定存在两条及以上的点不重复的路径。
实现
我们需要在 Tarjan 算法的过程中维护一个栈，并按照如下方法维护栈中的元素：
- 当一个节点第一次被访问时，将该节点入栈。
- 当遍历到一条树边 \(u \rightarrow v\) 满足 \(\operatorname{low}_v \geq \operatorname{dfn}_u\) 时（此时 \(u\) 为割点），不断弹出栈内元素直至节点 \(v\) 被弹出，所有被弹出的节点（以及节点 \(u\)）即为一个新的点双连通分量。
注意在弹栈的时候不能把节点 \(u\) 弹出，因为 \(u\) 可能属于多个点双。
void tarjan(int u, int last, bool isRoot) {
dfn[u] = low[u] = ++timer;
s.push(u);
int son = 0;
for (int i = head[u]; ~i; i = E[i].nxt) {
if (i == (last ^ 1)) continue;
int v = E[i].v;
if (!dfn[v]) {
son++; tarjan(v, i, false);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
vBCC_cnt++;
int p = 0;
do {
p = s.top(); s.pop();
vBCC[vBCC_cnt].push_back(p);
} while (p != v);
vBCC[vBCC_cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[v]);
}
if (isRoot && !son) { // 特判孤立点
vBCC_cnt++;
vBCC[vBCC_cnt].push_back(u);
}
}
割边
在无向图中，删去后使得连通分量数增加的边称为割边，也称桥。
孤立边是割边。
一条边 \(u \rightarrow v\) 是割边当且仅当：
- \(u \rightarrow v\) 是 dfs 树的树边。
- \(\operatorname{low}_v \gt \operatorname{dfn}_u\)。
void tarjan(int u, int last) {
dfn[u] = low[u] = ++timer;
for (int i = head[u]; ~i; i = E[i].nxt) {
if (i == (last ^ 1)) continue;
int v = E[i].v;
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) isBridge[i] = isBridge[i ^ 1] = true;
}
else low[u] = min(low[u], dfn[v]);
}
}
边双连通分量
边双连通图：不存在割边的无向连通图称为边双连通图。孤立点是边双连通图，但孤立边不是。
边双连通分量：一张图的极大边双连通子图称为边双连通分量（E-BCC），简称边双。
实现
删去所有割边后，剩下的连通分量即为边双连通分量。
void dfs(int u) {
vis[u] = true;
eBCC[eBCC_cnt].push_back(u);
for (int i = head[u]; ~i; i = E[i].nxt) {
if (isBridge[i]) continue;
int v = E[i].v;
if (!vis[v]) dfs(v);
}
}
强连通分量
定义一个强连通分量的根为该强连通分量中最浅的节点。
那么节点 \(u\) 为它所在强连通分量的根当且仅当 \(\operatorname{dfn}_u = \operatorname{low}_u\)。
实现
同样需要维护一个栈，并按照如下方法维护栈中的元素：
- 当一个节点第一次被访问时，将该节点入栈。
- 当点 \(u\) 满足 \(\operatorname{dfn}_u = \operatorname{low}_u\) 时，不断弹出栈内元素直至 \(u\) 被弹出，所有被弹出的节点即为一个强连通分量。
注意如果遍历到一个已经访问过的点 \(v\)，只有在栈内的 \(v\) 才能用来更新 \(\operatorname{low}_u\)。
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
s.push(u); inStack[u] = true;
for (int i = head[u]; ~i; i = E[i].nxt) {
int v = E[i].v;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (inStack[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
SCC_cnt++;
while (s.top() != u) {
SCC[SCC_cnt].push_back(s.top());
inStack[s.top()] = false; s.pop();
}
SCC[SCC_cnt].push_back(u);
inStack[u] = false; s.pop();
}
}