Poj 2186 Popular Cows(強連通成分)
13934 ワード
http://poj.org/problem?id=2186
tarjanで強い連通成分の個数を算出してその縮点を1本の木につなげると問題で求めたものが求出度0になるそのノードは木の中で唯一の木の根である
View Code
tarjanで強い連通成分の個数を算出してその縮点を1本の木につなげると問題で求めたものが求出度0になるそのノードは木の中で唯一の木の根である
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<stdlib.h>
6 #include<stack>
7 using namespace std;
8 #define M 50010
9 #define N 10010
10 struct node
11 {
12 int u,v,next;
13 }edge[M*2];
14 int head[N],lowlink[N],pre[N],t,sccno[N],scc,dep,dout[N];
15 stack<int>s;
16 void init()
17 {
18 t = 0;
19 memset(head,-1,sizeof(head));
20 memset(lowlink,0,sizeof(lowlink));
21 memset(pre,0,sizeof(pre));
22 memset(sccno,0,sizeof(sccno));
23 dep=0;scc=0;
24 }
25 void add(int u,int v)
26 {
27 edge[t].u = v;
28 edge[t].v = v;
29 edge[t].next = head[u];
30 head[u] = t++;
31 }
32 void dfs(int u)
33 {
34 lowlink[u] = pre[u] = ++dep;
35 s.push(u);
36 for(int i = head[u] ; i != -1 ; i = edge[i].next)
37 {
38 int v = edge[i].v;
39 if(!pre[v])
40 {
41 dfs(v);
42 lowlink[u] = min(lowlink[u],lowlink[v]);
43 }
44 else if(!sccno[v])
45 lowlink[u] = min(lowlink[u],pre[v]);
46 }
47 if(lowlink[u]==pre[u])
48 {
49 scc++;
50 for(;;)
51 {
52 int x = s.top();s.pop();
53 sccno[x] = scc;
54 if(x==u) break;
55 }
56 }
57 }
58 void find_scc(int n)
59 {
60 for(int i = 1 ; i <= n ; i++)
61 if(!pre[i]) dfs(i);
62 }
63 int main()
64 {
65 int i,j,n,m,a,b;
66 while(cin>>n>>m)
67 {
68 init();
69 while(m--)
70 {
71 cin>>a>>b;
72 add(a,b);
73 }
74 find_scc(n);
75 for(i = 1; i <= scc ; i++)
76 dout[i] = 0;
77 for(i = 1; i <= n ; i++)
78 for(j = head[i] ; j!=-1 ; j = edge[j].next)
79 {
80 int v = edge[j].v;
81 if(sccno[i]!=sccno[v])
82 dout[sccno[i]] = 1;
83 }
84 int num=0,o,w=0;
85 for(i = 1 ; i <= scc ; i++)
86 if(dout[i]==0)
87 {
88 o = i;
89 num++;
90 }
91 if(num==0)
92 cout<<n<<endl;
93 else if(num==1)
94 {
95 for(i = 1; i <= n ; i++)
96 if(sccno[i]==o)
97 {
98 w++;
99 }
100 cout<<w<<endl;
101 }
102 else
103 cout<<"0
";
104 }
105 return 0;
106 }View Code