void tarjan(int u, int fa) {
dfn[u] = low[u] = ++cnt;
ins[u] = 1, stk[++top] = u;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == fa) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else if (ins[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
p++;
int x;
do {
// 因为不需要知道每个边双连通分量里都有哪些点,只记录每个点属于哪个边双连通分量即可。
x = stk[top--];
ins[x] = 0;
bel[x] = p;
V[p]++; // 累加该边双连通分量内点数
} while (x != u);
}
}
上面本来是有向图的缩点,但加上下面这行代码就能过无向图的缩点:
if (v == fa) continue;