[图论] 求边双联通分量

定义

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

思路

我们之前已经学习了如何求割点和桥。

我们先用 $tarjan$ 算法求出所有的桥，然后通过 $dfs$ 的方式求出每一个点还未访问过的点不通过桥能走到哪些节点

这些节点组成的集合就是一个边双联通分量

代码

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

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

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

int n, m;
int bcc_cnt;
vector <int> ebcc[MAXM];

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
} 

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

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

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

        if(!dfn[v]){
            tarjan(v, x);

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

            if(low[v] > dfn[x]){
                isBridge[i] = isBridge[i^1] = 1;
            }
        }else if(dfn[v] < dfn[x] && v != f){
            low[x] = min(low[x], dfn[v]);
        }
    }
}

inline void dfs(int x, int bcc_number){
    dfn[x] = true;
    ebcc[bcc_number].push_back(x);

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

        if(isBridge[i]){
            continue;
        }

        if(!dfn[v]){
            dfs(v, bcc_number);
        }
    }
}

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

    memset(dfn, 0, sizeof(dfn));

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

inline void init(){
    memset(Head, -1, sizeof(Head));
    memset(Next, -1, sizeof(Next));
}