1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 7546 Solved: 4047
[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

HINT

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

Tarjan强连通分量

因为所有最受欢迎的牛，一定会互相欢迎最受欢迎的牛，所以所有最受欢迎的牛一定处在同一个强连通块中。

首先求出所有的强连通块，判断每条有向边是否属于不同的强连通块，如果属于不同的强连通块，则将发出这条边的强连通块的出度+1，（实际上就是将每个强连通块当作点来处理，也就是缩点）

最后判断是否存在出度为0的强连通块，如果只存在一个，则输出这个强连通块的数量。

如果存在多个则没有答案，输出0

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int MAXN=10000+5;
 6 const int MAXM=50000+5;
 7 struct Edge
 8 {
 9     int to,next;
10 }E[MAXM];
11 int node,head[MAXM];
12 int DFN[MAXN],LOW[MAXN],stack[MAXN];
13 int vis[MAXN],size[MAXN],f[MAXN],num[MAXN];
14 int index,top,tot,ans;
15 
16 int n,m;
17 
18 void insert(int u,int v)
19 {
20     E[++node]=(Edge){v,head[u]};head[u]=node;
21 }
22 
23 void tarjan(int x)
24 {
25     DFN[x]=LOW[x]=++index;
26     stack[++top]=x;
27     vis[x]=1;
28     for(int i=head[x];i;i=E[i].next)
29     {
30         if(!DFN[E[i].to])
31         {
32             tarjan(E[i].to);
33             LOW[x]=min(LOW[x],LOW[E[i].to]);
34         }
35         else if(vis[E[i].to])
36             LOW[x]=min(LOW[x],DFN[E[i].to]);
37     }
38     int now;
39     if(LOW[x]==DFN[x])
40     {
41         tot++;
42         do
43         {
44             now=stack[top--];
45             size[tot]++;
46             f[now]=tot;
47             vis[now]=0;
48         }while(x!=now);
49     }
50 }
51 
52 int main()
53 {
54     scanf("%d %d",&n,&m);
55     for(int i=1;i<=m;i++)
56     {
57         int a,b;
58         scanf("%d %d",&a,&b);
59         insert(a,b);
60     }
61     for(int i=1;i<=n;i++)
62         if(!DFN[i]) tarjan(i);
63     for(int i=1;i<=n;i++)
64         for(int j=head[i];j;j=E[j].next)
65             if(f[i]!=f[E[j].to])
66                 num[f[i]]++;
67     for(int i=1;i<=tot;i++)
68         if(!num[i])
69         {
70             if(ans)//不允许出现第二个出度为0的强联通块
71             {
72                 printf("0
");
73                 return 0;
74             }
75             ans=i;
76         }
77     printf("%d
",size[ans]);
78     return 0;
79 }