BZOJ 1051: [HAOI2006]受欢迎的牛

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 7120  Solved: 3779
[Submit][Status][Discuss]

Description

　　每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这

种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

Input

　　第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可

能出现多个A,B）

Output

　　一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

HINT

 

100%的数据N<=10000,M<=50000

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 const int maxn=50000+5;
 8 
 9 struct node{
10     int net;
11     int to;
12     int w;
13 }a[maxn*3];
14 int head[maxn],dfn[maxn],low[maxn],sum,ans,st[maxn],top;
15 int du[maxn],dep,cnt,tmp,rs[maxn],x[maxn],y[maxn],em[maxn];
16 bool vis[maxn];
17 int n,m;
18 int tt;
19 
20 inline void add(int x,int y)
21 {
22     a[++cnt].to=y;
23     a[cnt].net=head[x];
24     head[x]=cnt;
25 }
26 
27 void tarjan(int u)
28 {
29     ++dep;
30     low[u]=dfn[u]=dep;
31     st[++top]=u;
32     vis[u]=true;
33     for(int i=head[u];i;i=a[i].net)
34     {
35         int v=a[i].to;
36         if(!dfn[v])
37         {
38             tarjan(v);
39             low[u]=min(low[u],low[v]);
40         }
41         else if(vis[v])
42         {
43             low[u]=min(low[u],dfn[v]);
44         }
45     }
46     if(low[u]==dfn[u])
47     {
48         int now;
49         sum++;
50         do
51         {
52             now=st[top--];
53             rs[now]=sum;
54             vis[now]=0;
55             em[sum]++;
56         }while(now!=u);
57     }
58 }
59 
60 int main()
61 {
62     scanf("%d%d",&n,&m);
63     for(int i=1;i<=m;i++)
64     {
65         scanf("%d%d",&x[i],&y[i]);
66         add(x[i],y[i]);
67     }
68     for(int i=1;i<=n;i++)
69     {
70         if(!dfn[i])
71         {
72             tarjan(i);
73         }
74     }
75     for(int i=1;i<=n;i++)
76     {
77         for(int j=head[i];j;j=a[j].net)
78         {
79             int v=a[j].to;
80             if(rs[i]!=rs[v])
81             {
82                 du[rs[i]]++;
83             }
84         }
85     }
86     for(int i=1;i<=sum;i++)
87         if(!du[i])
88         {
89                if(tt)
90             {
91                 puts("0\n");
92                 return 0;
93             }
94                tt=i;
95            }
96     printf("%d\n",em[tt]);
97     return 0;
98 }