知识背景：首先明确强连通分量(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;
}
|
