[图论] 求点双联通分量

定义

在一个无向图中，如果不存在一个割点，那么我们称这个图是点双联通图。一个无向图中的每一个极大点双联通子图，称作点双联通分量

显然，每一个割点都会出现在两个点双联通分量中

思路

我们在上一篇文章中已经学习到了如何求出一个无向图的割点和桥

我们将 $dfs$ 过程中所有合法边都存入栈中，如果在 从 $x$ 到 $v$ 的 $dfs$ 过程时检查到了割点，那么我们就将 $x$ 到 $v$ 这条边上面所有的边弹出，两端节点组成的集合就是一个点双联通分量

注意：所有合法边即意味着反向边也要加入栈中

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;
const int MAXN = 100000 + 10;
const int MAXM = 200000 + 10;

int Head[MAXN], to[MAXM], Next[MAXM], tot = 1;
int dfn[MAXN], low[MAXN], time_stamp;

stack <pair<int, int> > Sta;

int bccNo[MAXN], bcc_cnt;
vector <int> bcc[MAXN];

int n, m;

inline void add(int a, int b){
    to[tot] = b;
    Next[tot] = Head[a];
    Head[a] = tot++;
}

inline void dfs(int x, int f){
    low[x] = dfn[x] = ++time_stamp;

    for(register int i=Head[x]; i; i=Next[i]){
        int v = to[i];

        if(!dfn[v]){
            Sta.push(make_pair(x, v));

            dfs(v, x);

            low[x] = min(low[x], low[v]);

            if(low[v] >= dfn[x]){
                bcc_cnt++;

                while(true){
                    pair<int, int> P = Sta.top();
                    Sta.pop();

                    if(bccNo[P.first] != bcc_cnt){
                        bcc[bcc_cnt].push_back(P.first);
                        bccNo[P.first] = bcc_cnt;
                    }

                    if(bccNo[P.second] != bcc_cnt){
                        bcc[bcc_cnt].push_back(P.second);
                        bccNo[P.second] = bcc_cnt;
                    }

                    if(P.first == x && P.second == v)
                        break;

                }               
            }
        }else if(dfn[v] < dfn[x] && v != f){
            Sta.push(make_pair(x, v));
            low[x] = min(low[x], dfn[v]);
        }
    }
}

inline void find_bcc(){
    for(register int i=1; i<=n; i++){
        if(!dfn[i])
            dfs(i, 0);
    }
}