POJ 2186 Popular Cows（强连通分量Kosaraju）

题意：

一个有向图，求出点的个数（任意点可达）。

思路：

Kosaraju算法的第一次dfs是后序遍历，而第二次遍历时遍历它的反向图，从标号最大的结点开始遍历。

对于这道题，在求解强连通分量之后，能被所有点可达只可能是最后一个强连通块，根据遍历时的拓扑序，我们可以计算出最后一个的结点个数。

但是我们最后还是要判断一下，这个连通块是不是任意结点可达。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 using namespace std;
11 
12 const int maxn=10000+5;
13 
14 int n,m;
15 vector<int> G[maxn];
16 vector<int> rG[maxn];
17 vector<int> vs;     //后序遍历顺序的顶点列表
18 int vis[maxn];
19 int sccno[maxn];   //所属强连通分量的拓扑序
20 int scc_cnt;       //强连通分量数量
21 
22 void add_edge(int from,int to)
23 {
24     G[from].push_back(to);
25     rG[to].push_back(from);
26 }
27 
28 void dfs1(int u)
29 {
30     if(vis[u])  return;
31     vis[u]=1;
32     for(int i=0;i<G[u].size();i++)   dfs1(G[u][i]);
33     vs.push_back(u);
34 }
35 
36 void dfs2(int u,int k)
37 {
38     if(sccno[u])  return;
39     sccno[u]=k;
40     for(int i=0;i<rG[u].size();i++)   dfs2(rG[u][i],k);
41 }
42 
43 void find_scc(int n)
44 {
45     scc_cnt=0;
46     vs.clear();
47     memset(sccno,0,sizeof(sccno));
48     memset(vis,0,sizeof(vis));
49     for(int i=0;i<n;i++)  if(!vis[i])  dfs1(i);
50     for(int i=n-1;i>=0;i--)
51     if(!sccno[vs[i]])  dfs2(vs[i],++scc_cnt);
52 }
53 
54 int main()
55 {
56     //freopen("D:\input.txt","r",stdin);
57     while(scanf("%d%d",&n,&m)!=EOF)
58     {
59         for(int i=0;i<m;i++)
60         {
61             int u,v;
62             scanf("%d%d",&u,&v);
63             u--; v--;
64             add_edge(u,v);
65         }
66         find_scc(n);
67         int u=0;
68         int ans=0;
69         //计算出最后一个强连通分量中点的数量
70         for(int i=0;i<n;i++)
71         {
72             if(sccno[i]==scc_cnt)
73             {
74                 u=i;
75                 ans++;
76             }
77         }
78         
79         //判断每个点是不是都能可达u
80         memset(sccno,0,sizeof(sccno));
81         dfs2(u,1);
82         for(int i=0;i<n;i++)
83         {
84             if(sccno[i]==0)
85             {
86                 ans=0;
87                 break;
88             }
89         }
90         printf("%d
",ans);
91     }
92     return 0;
93 }