Tarjian求无向图点双连通分量、边双连通分量

无向图求点双连通分量、边双连通分量

首先要知道什么是点双、边双：

点双：任意两点至少存在两条 ”点不重复“ 的路径。（内部无割点）
边双：每条边至少在一个简单环里。（所有边都不是桥）

举个例子：下面图中点双分量有两个{1，2，3}、{3，4，5}，但是只有一个边双分量{1， 2， 3，4 ，5}。

求点双分量

代码跟求割点类似，不过要加一个栈保存经过的边，每次遇到割点就将当前栈里面输出，即为一个点双分量。

书上代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fuck(x) cout<<x<<endl
const int N = 1e3 + 10;
const int mod = 998244353;

struct edge{
    int u, v;
};
int pre[N], iscut[N], bccno[N], dfs_clock, bcc_cnt;
vector<int> G[N], bcc[N];

stack<edge> s;

int dfs(int u, int fa){
    int lowu = pre[u] = ++dfs_clock;
    int son = 0;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        edge e = edge{u, v};
        if(!pre[v]){
            s.push(e);
            son++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);     // 用后代的 low 更新自己
            if(lowv >= pre[u]){
                iscut[u] = 1;
                bcc[++bcc_cnt].clear();
                while(1){
                    edge x = s.top();
                    s.pop();
                    if(bccno[x.u] != bcc_cnt){
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt){
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v] = bcc_cnt;
                    }
                    if(x.u == u && x.v == v)
                        break;
                }
            }
        }else if(pre[v] < pre[u] && v != fa){
            s.push(e);
            lowu = min(lowu, pre[v]);
        }
    }
    if(fa < 0 && son == 1)
        iscut[u] = 0;
    return lowu;
}

void find_bcc(int n){
    memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!pre[i]){
            dfs(i, -1);
        }
    }
}

int main(){

    find_bcc(6);
    for(int i = 0; i <= bcc_cnt; i++){
		for (auto x : bcc[i]){
			printf("%d ", x);
		}
		puts("");
	}
}

模板代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fuck(x) cout<<x<<endl
const int N = 1e3 + 10;
const int mod = 998244353;

int ne[N], h[N], to[N], fr[N], idx;			// 存图
int pre[N], iscut[N], bccno[N], low[N], dfs_clock, bcc_cnt;	
// 开始时间戳、割点、bccno[i] 表示点 i 所在的分量（vector）
vector<int> bcc[N];	// 每个 vector 保存一个点双分量
stack<int> s;

void add(int u, int v){
	fr[idx] = u, to[idx] = v, ne[idx] = h[u], h[u] = idx++;
	fr[idx] = v, to[idx] = u, ne[idx] = h[v], h[v] = idx++;
}

void dfs(int u, int fa){
	low[u] = pre[u] = ++dfs_clock;
	int son = 0;
	for(int i = h[u]; ~i; i = ne[i]){
		int v = to[i];
		if(!pre[v]){
			s.push(i), son++;
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= pre[u]){	// u 是割点，栈里面的边都是一个点双分量
				iscut[u] = 1;
				bcc[++bcc_cnt].clear();
				while(1){
					int x = s.top();
					s.pop();
					if(bccno[fr[x]] != bcc_cnt){
						bcc[bcc_cnt].push_back(fr[x]);
						bccno[fr[x]] = bcc_cnt;
					}
					if(bccno[to[x]] != bcc_cnt){
						bcc[bcc_cnt].push_back(to[x]);
						bccno[to[x]] = bcc_cnt;
					}
					if(x == i) break;
				}
			}
		}else if(v != fa && pre[v] < low[u]){
			s.push(i);
			low[u] = pre[v];
		}
	}
	if(fa < 0 && son == 1)
		iscut[u] = 0;
}

void find_bcc(int n){
	memset(low, 0, sizeof(low));
	memset(pre, 0, sizeof(pre));
    memset(iscut, 0, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = bcc_cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!pre[i]){
            dfs(i, -1);
        }
    }
}

int main(){
	memset(h, -1, sizeof(h));
	// add(u, v)	// 加边
	for(int i = 1; i <= bcc_cnt; i++){	// 输出每个分量
		for (auto x : bcc[i]){
			printf("%d ", x);
		}
		puts("");
	}
}

边双连通分量

分两个步骤：
先做一次 $dfs$dfs 标记处所有的桥
然后再做一次 $dfs$dfs 找出边双。（不经过桥，以桥分割的分量）