定义

在无向图G=(V,E)中，如果删除任意一个节点（及其关联的边）后，子图仍然连通，则称这个子图是点连通的。

点双连通分量（Vertex Biconnected Component, vDCC）：图的极大点连通子图。

重要性质：

1. 点双连通分量内部没有割点
2. 不同的点双连通分量之间通过割点连接
3. 一个割点可以属于多个点双连通分量
4. 点双连通分量和割点一起可以构成块-割点树

Tarjan算法求点双连通分量

1. 算法核心思想

Tarjan算法基于深度优先搜索（DFS），是求割点算法的扩展。核心思想是：

1. 在DFS过程中维护一个栈，存储当前搜索路径上的节点
2. 当发现一个割点时，从栈中弹出节点直到当前节点的子节点
3. 弹出的节点与割点一起构成一个点双连通分量
4. 注意：割点不出栈，因为它可能属于多个分量

2. 算法流程

// 核心判断条件
if(low[to] >= dfn[u]) { // 发现割点u的一个vDCC
++tot; // 新增一个点双连通分量
int v;
do {
v = stk.top();
stk.pop();
Dcc[tot].push_back(v);
} while(v != to); // 弹出直到子节点to
Dcc[tot].push_back(u); // 割点u也加入分量
}

模板

说明:void Run(int _n,vector<int> adj[])传入总点数n，vector<int>[]邻接表adj,运行Tarjan求点双联通分量。vector<int> Dcc[N] Dcc[i]存了编号为i的vDcc内所有的点.

template<int N> struct vDCC {
    int dfn[N],low[N];          
    const vector<int>* adj;        
    vector<int> stk,cut;                
    vector<int> Dcc[N]; //1~tot,Dcc[i]，编号为i的vDcc内的点.
    int tot; //vDcc数量      
    int n,clk,root;              
    void dfs(int u) {
        dfn[u]=low[u]=++clk;
        stk.push_back(u);
        int cnt=0;
        for (int to:adj[u]) {
            if (dfn[to]==0) {          
                dfs(to);
                low[u]=min(low[u], low[to]);
                if (low[to]>=dfn[u]){
                    ++cnt;
                    ++tot;
                    int v;
                    do{
                        v=stk.back();
                        stk.pop_back();
                        Dcc[tot].emplace_back(v);
                    }while(v!=to);
                    Dcc[tot].emplace_back(u);
                }
            }
            else low[u]=min(low[u],dfn[to]);  
        }
        if((u!=root && cnt>=1) || cnt>=2) cut[u]=true;
        if(cnt==0 && u==root) Dcc[++tot].pb(u);
    }
    void Run(int _n,vector<int> adj[]) {
        n=_n;
        this->adj=adj;
        clk=tot=0;
        fill(dfn,dfn+n+3,0);
        fill(low,low+n+3,0);
        stk.clear();
        cut.assign(n+3,false);
        for(int i=0;i<=n+3;++i) Dcc[i].clear();
        for (int i=1;i<=n;++i){
            if(dfn[i]==0) {root=i; dfs(i);}
         }
    }
};
const int maxn=2*1e5+20;
vDCC<maxn> T;