思路

首先，点双连通分量就是删去任意一点后仍连通的分量。

如何求呢？看着定义，答案就已经在里面了——求出割点即可。

与边双不同的是，点双中是包括割点的。

究其原因，删去割点之后，原图会被分成多个连通块，但事实上，割点加入其中任意一个，仍然是双连通的。证明如下：

• 若连通块到割点有多条边，毫无疑问。
• 若割点是独立点，那么它单独为一个点双。
• 若连通块到割点只有一边——额外，设这个连通块在割点下面，也就是说，它属于割点的某一棵子树——那么，这个子结点也是一个割点，这两个割点可以构成一个双连通分量。

所以，一个割点可以同时属于所有被它割的双连通分量——包括它的父节点所在的连通块。

我们可以考虑在找割点的时候，实时进行判断，假如找到了一个子树被当前节点割，那么就把它们加到一个双连通分量中。

不会找割点点这里。

细节

由于我们要找分量，毫无疑问，就需要借助栈，来获取它的子树。

需要注意的是，由于当前节点同时属于多个连通分量，所以在弹出的时候不应该把它自己也弹出，只需要把被它割走的子树全部弹出。别忘了最后额外把当前节点也加入那个连通块之中。

与找割点不同的是，我们不需要额外地判断根节点是否是一个割点，因为即使根节点只有一个子树，它同样满足上述性质，并且需要被加入连通块中。

换种说法，就算根节点只有一棵子树，我们也需要把它加入它子树的连通块中。

额外地，我们需要特殊判定独立点，因为它没有子树，无法在算法中自动加入连通块。

任何对找连通块原理不理解的都可以看求强连通分量来借鉴思路。不过那是有向图，所以要判断是不是 \(双向奔赴\) ，不要和点双边双搞混了。

使用栈储存，记得在一轮Tarjan结束后额外弹出根节点——你应该没忘这句话吧？

需要注意的是，由于当前节点同时属于多个连通分量，所以在弹出的时候不应该把它自己也弹出，只需要把被它割走的子树全部弹出。别忘了最后额外把当前节点也加入那个连通块之中。

模板

int dcnt;
int dfn[N],low[N];
bool flag[N];
stack<int> stk;
int bcnt;
vector<int> bcc[N];
void tarjan(int x,int fa){
    dfn[x]=low[x]=++dcnt;
    stk.push(x);
    int ccnt=0;
    for(int e=hd[x];e;e=ne[e]){
        int nxt=to[e];
        if(!dfn[nxt]){
            ++ccnt;
            tarjan(nxt,x);
            low[x]=min(low[x],low[nxt]);
            if(low[nxt]>=dfn[x]){
                ++bcnt;
                while(1){
                    int tp=stk.top();stk.pop();
                    bcc[bcnt].push_back(tp);
                    if(tp==nxt)break;
                }
                bcc[bcnt].push_back(x);
            }
        }else low[x]=min(low[x],dfn[nxt]);
    }
    if(x==fa&&ccnt==0){
        ++bcnt;
        bcc[bcnt].push_back(x);
    }
}

例题

LG8435

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

typedef vector<int> veci;

const int N=5e5+5,M=2e6+5;

int n,m;

int cnt;
int hd[N],ne[M*2],to[M*2];
void adde(int a,int b){
    to[++cnt]=b;
    ne[cnt]=hd[a];
    hd[a]=cnt;
}

int dcnt;
int dfn[N],low[N];
bool flag[N];
stack<int> stk;
int bcnt;
vector<int> bcc[N];
void tarjan(int x,int fa){
    dfn[x]=low[x]=++dcnt;
    stk.push(x);
    int ccnt=0;
    for(int e=hd[x];e;e=ne[e]){
        int nxt=to[e];
        if(!dfn[nxt]){
            ++ccnt;
            tarjan(nxt,x);
            low[x]=min(low[x],low[nxt]);
            if(low[nxt]>=dfn[x]){
                ++bcnt;
                while(1){
                    int tp=stk.top();stk.pop();
                    bcc[bcnt].push_back(tp);
                    if(tp==nxt)break;
                }
                bcc[bcnt].push_back(x);
            }
        }else low[x]=min(low[x],dfn[nxt]);
    }
    if(x==fa&&ccnt==0){
        ++bcnt;
        bcc[bcnt].push_back(x);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        adde(a,b);
        adde(b,a);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i,i);
            stk.pop();
        }
    }
    cout<<bcnt<<"\n";
    for(int i=1;i<=bcnt;i++){
        cout<<bcc[i].size()<<" ";
        for(auto j:bcc[i])cout<<j<<" ";
        cout<<"\n";
    }
    return 0;
}