P8435 【模板】点双连通分量题解

lrqlrq250 · 2022-07-13 13:27:02 · 题解

点双连通分量

前置芝士：割点的 Tarjan 算法。

在阅读本题解前，请确保您已经完全理解了前置芝士中提到的概念。

1.定义

一张无向图是点双连通图，当且仅当其满足下列两个条件之一：

图的顶点数量不超过 2 个。
图中的任意两点都同时包含在至少一个简单环中。

其中第二个条件等价于这张无向图中没有割点。

一张无向图的极大点双联通子图被称为点双连通分量（v-DCC）。

注意：有部分读者可能已经做过 BLO-Blockade 这道题，请千万注意，点双连通分量的定义与这道题中“删除所有割点后图中剩余的连通块”是完全不同的（实际上边双是类似这么定义的，但点双不是）。一张无向图的点双连通分量可以包含该图中的割点。

2.求法

既然和连通分量有关系，自然是逃不过 Tarjan 算法。为了求出点双连通分量，我们在执行求割点的 Tarjan 算法的过程中按如下方法维护一个栈：

当节点 x 第一次被访问时，将其入栈。
当节点 x 满足割点判断条件 dfn[x] \le low[y] 时，无论 x 是否是根节点，都要不断从栈中弹出节点，直到弹出节点 y。此时刚才弹出的所有节点和节点 x 共同构成了一个点双连通分量。

3.正确性证明（原理）

回顾一下求割点的过程，可以发现其实我们在求出割点的过程中就已经“顺便”遍历了该割点属于的点双。根据割点的定义，当满足 dfn[x] \le low[y] 时，就说明以 y 为根的子树中没有节点可以通过至多一条边回到在 y 之前访问过的节点，最多就是绕一圈回到 y。因此如果把 y 断掉，y 和下方的节点就独立了。这就是一个点双连通分量。

根据 Tarjan 算法的流程，我们每找到一个割点，栈中在该割点上方的一定是以该节点为根的子树。不断弹出栈中节点，该子树和当前访问的节点就构成了一个点双。

理解了上述所有内容后，这道题就没有任何难度了，我们使用一个 vector 数组来记录每个点双连通分量就可以满足输出条件了。

AC Code

#include <bits/stdc++.h>
using namespace std;
struct Edge{int to, next;}e[4000001];
int n, m, head[500001], tot, rt;
int dfn[500001], low[500001], num, cnt;
bool cut[500001];
stack<int> stk;
vector<int> dcc[2000001];

inline void addedge(int u, int v){
    e[++tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

void tarjan(int x){
    dfn[x] = low[x] = ++num;
    stk.push(x);
    if (x == rt && !head[x]){dcc[++cnt].push_back(x); return;}//注意孤立点也是一个点双，别问为什么，这是定义……
    int flg = 0;
    for (int i=head[x], y; i; i=e[i].next){
        y = e[i].to;
        if (!dfn[y]){
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]){
                flg++;
                if (x != rt || flg >= 2) cut[x] = 1;//说明x是割点了
                cnt++;
                int z;
                do{
                    z = stk.top(); stk.pop();
                    dcc[cnt].push_back(z);
                } while (y != z);
                dcc[cnt].push_back(x);//千万不要忘了这个，必须要加上x才是一个点双连通分量
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i=1; i<=m; i++){
        scanf("%d%d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    for (int i=1; i<=n; i++) if (!dfn[i]) rt = i, tarjan(i);
    printf("%d\n", cnt);
    for (int i=1; i<=cnt; i++){
        printf("%d ", dcc[i].size());
        for (int j=0; j<dcc[i].size(); j++) printf("%d ", dcc[i][j]);
        printf("\n");
    }
    return 0;
}

部分严格定义和代码来自李煜东《算法竞赛进阶指南》。

P8435 【模板】点双连通分量 题解