描述
yuyu心情不太好，于是她进入了自己的虚拟世界，其中有n个小镇(1~n编号)和m条单向道，她随便选了一个点，沿着道路往前走，她发现自己可以无限的一直走下去，正好用来打发她的时间。现在她想知道，这个世界中能有几个这样的出发点，只要她选择合适的道路，总可能让她这样一直走下去。
输入
第一行为正整数n和m，表示小镇数目和路的条数(1≤n≤2·105, 0≤m≤min(n(n-1), 2·105))。
之后有m行，每行两个正整数u和v(1≤u, v≤n, u≠v)，表示从u到v有一条单向道路，道路不存在重复。
输出
输出可能的小镇数目。
样例输入
5 5
1 2
2 3
3 4
4 2
4 5
样例输出
4 思路： 本来是想用拓扑找环，再反向构图从环出发找能走的点，但是没曾想原来拓扑只能用来判断有无环，并不能准确的找到环，所以错了N多遍。。。 最后用的kosaraju算法先正向dfs遍历，将每次退出时的点入栈，然后再按出栈的顺序来dfs遍历反向图，并且把遍历到的点都用cmp数组标记上是第k个环，而且计算第k个环出现了vis[k]次，最后再遍历V个点，对于第i个点所属的环是cmp[i]，而这个环出现了vis[cmp[i]]次，如果次数大于1证明是环，从这个点出发反向dfs把能走到的点都算上，最终就是答案
1 #include<iostream>
2 #include<cstdio>
3 #include<vector>
4 #include<cstring>
5
6 using namespace std;
7
8 const int max_v=200010;
9
10 int V;
11 vector<int>g[max_v];
12 vector<int>rg[max_v];
13 vector<int>vs;
14 bool used[max_v];
15 int cmp[max_v];
16 int vis[max_v],ans,vis2[max_v];
17 void add_edge(int from,int to)
18 {
19 g[from].push_back(to);
20 rg[to].push_back(from);
21 }
22
23 void dfs(int v)
24 {
25 used[v]=true;
26 for(int i=0;i<g[v].size();i++){
27 if(!used[g[v][i]]){
28 dfs(g[v][i]);
29 }
30 }
31 vs.push_back(v);
32 }
33
34 void rdfs(int v,int k)
35 {
36 used[v]=true;
37 cmp[v]=k;
38
39 for(int i=0;i<rg[v].size();i++){
40 if(!used[rg[v][i]]){
41 vis[k]++;
42 rdfs(rg[v][i],k);
43
44 }
45 }
46 }
47
48 void scc()
49 {
50 memset(used,0,sizeof(used));
51 vs.clear();
52 for(int v=1;v<=V;v++){
53 if(!used[v]){
54 dfs(v);
55 }
56 }
57 memset(used,0,sizeof(used));
58 int k=0;
59 for(int i=vs.size()-1;i>=0;i--){
60 if(!used[vs[i]]){
61 vis[++k]++;
62 rdfs(vs[i],k);
63 }
64 }
65 }
66 void solve(int x)
67 {
68 for(int i=0;i<rg[x].size();i++)
69 {
70 int tx = rg[x][i];
71 if(vis2[tx]==0)
72 {
73 ans++;
74 vis2[tx] = 1;
75 solve(tx);
76 }
77 }
78 }
79 int main()
80 {
81 scanf("%d",&V);
82 int m;
83 scanf("%d",&m);
84 int u,v;
85 for(int i=0;i<m;i++){
86 scanf("%d%d",&u,&v);
87 add_edge(u,v);
88 }
89 scc();
90 for(int i=1;i<=V;i++)
91 {
92 if(vis[cmp[i]]>1 && vis2[i]==0)
93 {
94 ans++;
95 vis2[i] = 1;
96 solve(i);
97 }
98 }
99
100 printf("%d\n",ans);
101 return 0;
102 }
103 /*
104 12
105 16
106 12 11
107 11 8
108 11 10
109 8 10
110 10 9
111 9 8
112 9 7
113 7 6
114 5 7
115 6 5
116 6 4
117 6 3
118 4 3
119 2 3
120 3 2
121 4 1
122 */
标签：int,max,8064,dfs,vis,kosaraju,yuyu,include,cmp From： https://www.cnblogs.com/jyssh/p/17273627.html