强连通分量模板

Posted on | In ,

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图 的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。

实现算法：两次dfs，第一次 dfs 遍历将顶点后序(post order)记录下来vs（vector），这里需要注意的是，不管从哪个点dfs，由于是后序记录，故最终得到的记录是一样的，vs中的顶点（按下标）从前至后对应在DAG中为从尾到头。第二次dfs对于vs中的元素从尾到头进行，使用反向边，故每次dfs只能访问到同一个强连通分量。因而每次dfs时给所到顶点加上一个表示第几个scc的标号，即可完成对该图的分解。

例题：poj2186

每头羊有若干崇拜对象，并且崇拜关系可传递，求出被其他所有羊崇拜的羊的个数。

即求最后一个scc所含顶点个数。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

int n,m;
vector<int> g[10001];
vector<int> rg[10001];
bool used[10001];
vector<int> vs;
int cmp[10001];

void dfs(int v) {
	used[v]=true;
	for(int i=0; i<g[v].size(); i++)
		if(!used[g[v][i]])
			dfs(g[v][i]);
	vs.push_back(v);
}

void rdfs(int v,int k) {
	used[v]=true;
	cmp[v]=k;
	for(int i=0; i<rg[v].size(); i++)
		if(!used[rg[v][i]])
			rdfs(rg[v][i],k);
}

int scc() {		//strongly connected component
	memset(used,0,sizeof(used));
	vs.clear();
	for(int i=0; i<n; i++)
		if(!used[i])
			dfs(i);
	int k=0;
	memset(used,0,sizeof(used));
	for(int i=vs.size()-1; i>=0; i--)
		if(!used[vs[i]])
			rdfs(vs[i],k++);        //最开始把vs[i]错写成i，把属于不同块的顶点打上了相同标号
	return k;
}

int main() {
	while(cin>>n>>m) {
		int to,from;
		for(int i=0; i<m; i++) {
			cin>>from>>to;
			g[from-1].push_back(to-1);
			rg[to-1].push_back(from-1);
		}
		int num=scc();
		int u,res=0;
		for(int i=0; i<n; i++) {
			if(cmp[i]==num-1) {
				res++;
				u=i;
			}
		}
		memset(used,0,sizeof(used));
		rdfs(u,0);
		for(int i=0; i<n; i++) {
			if(!used[i]) {
				res=0;
				break;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}