感言：

瑟瑟发抖的萌新好不容易A掉了这道14个人才过掉的题，然而被杨树神无情抢沙发，仅仅慢了十几分钟……已经哭晕在厕所……

为什么要拉出来这道题呢，因为刚刚刷完割边割点强连通分量，所以就写写这道题试一试，而且发现了一些新的技巧，神奇的缩点和最后答案的判断……

最受欢迎的牛

题目描述：

每头牛都有一个梦想：成为一个群体中最受欢迎的名牛！在一个有N(1<=N<=10,000)头牛的牛群中，给你M(1<=M<=50,000)个二元组(A,B),表示A认为B是受欢迎的。既然受欢迎是可传递的，那么如果A认为B受欢迎，B又认为C受欢迎,则A也会认为C是受欢迎的，哪怕这不是十分明确的规定。你的任务是计算被所有其它的牛都喜欢的牛的个数。

输入：

第一行，两个数，N和M。第2～M+1行，每行两个数，A和B，表示A认为B是受欢迎的；

输出：

一行，最受欢迎的奶牛的数量……

题解：

这道题用到了tarjan算法，用这个算法来求出所有的联通分量，为什么要求联通分量呢，因为每一个连通分量中，因为我喜欢你，你也喜欢我，那么我们两个就可以看成一个点，这样就可以吧五万个点缩成不同的连通分量，大大减少运算。

然后缩成了连通分量之后，就可以把他们当成每一个点，如果图中有且仅有一个点的出度为零，那么这个点中的所有元素就都是万众仰慕的牛了！输出元素数量就好。

那么为什么有且仅有一个点的出度为零就确定了这个集合呢，因为如果出度如果没有一个为零，那么这个图就仅仅有一个点，点里面包含的所有点都是满足条件的点，所有的牛都喜欢对方（形成了环），如果有多个点出度为零，那么就没有集合是满足条件的了，因为如果多个点出度为零，那么一定有其中的一个点不喜欢其他牛，那么就没有办法找到所有牛都喜欢的牛了,因此我们只需要判断点的出度就可以了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct Edge
{
    int x;
    int y;
    int next;
};
Edge a[50001];
int n,m,xx,yy,Link[10001],len=0;
int low[50001],dfn[50001],ind=0;
int stack[50001],top=0,tot=0;
int all[50001],bel[50001];
int Out_point[50001],ans;
bool ins[50001],GG=false;
void init(int xx,int yy)
{
    a[++len].x=xx;
    a[len].y=yy;
    a[len].next=Link[xx];
    Link[xx]=len;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++ind;
    stack[++top]=x;
    ins[x]=true;
    for(int i=Link[x];i!=0;i=a[i].next)
    {
        int y=a[i].y;
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[y],low[x]);
        }else if(ins[y]==true)
        low[x]=min(low[x],low[y]);
    }
    if(low[x]==dfn[x])
    {
        int k;
        tot++;
        do
        {
            all[tot]++;
            k=stack[top--];
            ins[k]=false;
            bel[k]=tot;
        }while(k!=x);
    }
}
int main()
{
    memset(Link,0,sizeof(Link));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(stack,0,sizeof(stack));
    memset(ins,false,sizeof(ins));
    memset(bel,0,sizeof(bel));
    memset(all,0,sizeof(all));
    memset(Out_point,0,sizeof(Out_point));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>xx>>yy;
        init(xx,yy);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i]) tarjan(i);
    for(int i=1;i<=len;i++)
    {
        if(bel[a[i].x]==bel[a[i].y])
        continue;
        else if(bel[a[i].x]!=bel[a[i].y])
        {
           Out_point[bel[a[i].x]]++;
           //cout<<bel[a[i].x]<<' '<<a[i].x<<' '<<Out_point[bel[a[i].x]]++<<endl;
        }
    }
    ans=n;
    for(int i=1;i<=tot;i++)
    {
        if(Out_point[i]==0)
        {
            if(GG==false)
            {
                GG=true;
                ans=all[i];
            }
            else if(GG==true)
            {
                ans=0;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}