无向图的连通性

发表于 更新于 分类于 本文字数： 557 阅读时长 ≈ 2 分钟
无向图的割边、割点、便双连通分量

割边

以P1656 炸铁路为例，核心部分为：

1
2
3
4
5
6
7
8
9
if(!dfn[v]){
    tarjan(v,x);
    low[x]=min(low[x],low[v]);
    if(low[v]>dfn[x]){
        ve.push_back(make_pair(x,v));
    }
}else{
    low[x]=min(low[x],dfn[v]);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int N=152,M=5003;
int head[N],nxt[M],to[M],num=0;
void add(int a,int b){
	num++;
	to[num]=b;
	nxt[num]=head[a];
	head[a]=num;
}
int dfn[N],low[N],cnt=0;
vector<pair<int,int>>ve;
void tarjan(int x,int f){
	dfn[x]=low[x]=++cnt;
	for(int i=head[x];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		if(!dfn[v]){
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
			if(low[v]>dfn[x]){
				ve.push_back(make_pair(x,v));
			}
		}else{
			low[x]=min(low[x],dfn[v]);
		}
	} 
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	sort(ve.begin(),ve.end());
	for(auto i:ve){
		cout<<min(i.first,i.second)<<" "<<max(i.first,i.second)<<endl;
	}
	return 0;
}

割点

以P3388 【模板】割点（割顶）为例，核心部分为：

1
2
3
4
5
6
7
8
9
10
if(!dfn[v]){
    tarjan(v,x);
    low[x]=min(low[x],low[v]);
    if(low[v]>=dfn[x]){
        tot++;
        if(tot>=2||f!=0)ve.insert(x);
    }
}else{
    low[x]=min(low[x],dfn[v]);
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
using namespace std;
const int N=2e4+4,M=2e5+5;
int head[N],nxt[M],to[M],num=0;
void add(int a,int b){
	num++;
	to[num]=b;
	nxt[num]=head[a];
	head[a]=num;
}
int dfn[N],low[N],cnt=0;
set<int>ve;
void tarjan(int x,int f){
	dfn[x]=low[x]=++cnt;
	int tot=0;
	for(int i=head[x];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		if(!dfn[v]){//cout<<x<<" "<<v<<endl;
			tarjan(v,x);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x]){
				tot++;
				if(tot>=2||f!=0)ve.insert(x);
			}
		}else{
			low[x]=min(low[x],dfn[v]);
		}
	} 
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	cout<<ve.size()<<endl;
	for(auto i:ve){
		cout<<i<<" ";
	}
	return 0;
}

边双连通分量

桥两端的节点一定不是同一个边双连通分量的节点

1
2
3
4
5
6
7
8
void fb(int u) {
    bl[u] = dcc;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (bl[v] || br[i]) continue;
        fb(v);
    }
}
// in int main()
for (int i = 1; i <= n; i++) {
	if (!bl[i]) {
		dcc++;
		fb(i);
	}
}
在同一个边双连通分量的节点就可以缩点了。