点双详解

· · 题解

概念： 点双连通分量（vertex double connected components)

简称点双。在一个无向图的点双连通分量中，删除任意一点，剩下的所有点仍然互相连通。举个例子：

这是一个点双，删除其中任何一点，剩下的点依然联通。

而这就不是点双了，因为删除节点 3 将把整张图分为两半。

割点

在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点。因此点双中没有割点。

算法：Tarjan

此算法的发明者为美国计算机科学家 Robert Tarjan。

核心思路：DFS ，当一个点往下无法到达之前搜过的点时，说明该点分割了图，如第二个样例中的点 3。

具体实现：记录每个点的搜索顺序 dfn，每个点不往之前走过的点走可以到达的 dfn 最小的点 low（表达能力极差QAQ）。

模拟这张图，从任意一点（图中为点 1）开始搜索：

红色标记为每个点的 dfn，为其 DFS 到达的顺序。

我们对于每一个点 x，将 low[x] 设置为 dfn[x] 并枚举它能到达的点 y（除了他的上一个点，如本图中在 dfs 到 5 时，我们忽略了 4）：

图中点 5 搜到了点 3 ，原本 low[5] = dfn[5] = 5 ，low[3] = dfn[3] = 3 ，取 \operatorname{min} 后 low[5] = 3 （low 用绿色标记)。

如此，全过程如下：

绿色箭头表示用 low[y] 更新 low[x] ，紫色箭头则表示用 dfn[y] 更新 low[x]。

不妨认为我们在 DFS 时建了一棵树，那么当一个节点的子节点在之前未被搜索且 low[y] \geq dfn[x] 时，说明该子节点无法绕过该点前往该点上方的点。这个点就应该是一个割点（对于整个连通块来说）。这个割点显然属于所分割的两个连通块。

那么如何记录每个点双呢？开一个栈记录每一次 DFS 进入的点，满足条件时弹栈直到找到该点的子节点（毕竟该点在上方的点双还要被算一遍）。弹出的元素加上该点本身即为一个新的点双。

图中在 3、1 点依次弹栈。

代码如下：

#include<bits/stdc++.h>
using namespace std;

#define isdigit(x) ('0' <= x && x <= '9')
template<typename types>
inline void read(types &x){
    x = 0; int f = 1; char c;
    while ((c = getchar()) && !isdigit(c)) if (c == '-') f = -1;
    x = c ^ 48;
    while ((c = getchar()) && isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48);
    x *= f; return; 
}
template<typename types>
void write(types x){
    if (x < 0) putchar('-'), x = - x;
    types k = x / 10;
    if (k) write(k);
    putchar(x - (k << 3) - (k << 1) | 48);
    return;
}

const int MAXN = 500010;
const int MAXM = 4000010;

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], idx = 1;
int dfn[MAXN], low[MAXN], timecnt;    // timecnt 时间戳记录顺序 
vector<int> vdcc[MAXN];
int vdcc_cnt;
stack<int> s;

inline void addedge(int x, int y){
    nxt[++idx] = head[x];
    to[idx] = y;
    head[x] = idx;
    return;
}

void Tarjan(int x, int from){
    dfn[x] = low[x] = ++timecnt;
    s.push(x);
    int child = 0;
    int p;
    for (int i = head[x]; i; i = nxt[i]){
        if (i == (from ^ 1)) continue;    // 判断来路 
        child++;
        int y = to[i];
        if (!dfn[y]){
            Tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]){    // 找到点双 
                ++vdcc_cnt;
                do{
                    p = s.top(); s.pop();
                    vdcc[vdcc_cnt].push_back(p);
                } while (p != y);    // 弹到子节点 
                vdcc[vdcc_cnt].push_back(x);    // 记得把自己加进去 
            }
        }
        low[x] = min(low[x], dfn[y]);
    }
    if (!child && !from)    // 记得特判孤立点 
        vdcc[++vdcc_cnt].push_back(x);
    return;
}

int main(){
    read(n), read(m);
    int x, y;
    for (int i = 1; i <= m; ++i){
        read(x), read(y);
        if (x != y) addedge(x, y), addedge(y, x);
    }

    for (int i = 1; i <= n; ++i) if (!dfn[i]) Tarjan(i, 0); 

    write(vdcc_cnt), putchar('\n');
    for (int i = 1; i <= vdcc_cnt; ++i){
        write(vdcc[i].size()), putchar(' ');
        for (auto j = vdcc[i].begin(); j != vdcc[i].end(); ++j){
            write(*j), putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}