1051. [HAOI2006]受欢迎的牛【强连通分量】

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模板题……问题是垃圾LXXGU的数据太恶心
竟然有多个图的数据（强行给自己的菜开脱）
这个题就是将图缩点缩成一个有向无环图
若只有一个点出度为0那么这个点必然被所有牛喜欢
反证：要是有多个点出度为0，那么这些出度为0的点必然不会喜欢其他出度为0的点

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #define MAXN (100000+5)
 6 #define MAXM (100000+5)
 7 using namespace std;
 8 int Dfn[MAXN],Low[MAXN],Outd[MAXN];
 9 int Dfs_num,Col_num,Color[MAXN],Cnt[MAXN];
10 int u[MAXM],v[MAXM];
11 int stack[MAXN],top;
12 bool Vis[MAXN];
13 int head[MAXN],num_edge;
14 struct node
15 {
16     int next;
17     int to;
18 } edge[MAXM*2];
19 
20 void add(int u,int v)
21 {
22     edge[++num_edge].to=v;
23     edge[num_edge].next=head[u];
24     head[u]=num_edge;
25 }
26 
27 void Tarjan(int x)
28 {
29     Dfn[x]=++Dfs_num;
30     Low[x]=Dfs_num;
31     Vis[x]=true;
32     stack[++top]=x;
33     for (int i=head[x]; i!=0; i=edge[i].next)
34         if (!Dfn[edge[i].to])
35         {
36             Tarjan(edge[i].to);
37             Low[x]=min(Low[x],Low[edge[i].to]);
38         }
39         else if (Vis[edge[i].to])
40             Low[x]=min(Low[x],Dfn[edge[i].to]);
41     if (Dfn[x]==Low[x])
42     {
43         Vis[x]=false;
44         Color[x]=++Col_num;
45         Cnt[Col_num]++;
46         while (stack[top]!=x)
47         {
48             Cnt[Col_num]++;
49             Color[stack[top]]=Col_num;
50             Vis[stack[top--]]=false;
51         }
52         --top;
53     }
54 }
55 int main()
56 {
57     int n,m;
58     scanf("%d%d",&n,&m);
59     for (int i=1; i<=m; ++i)
60     {
61         scanf("%d%d",&u[i],&v[i]);
62         add(u[i],v[i]);
63     }
64     for (int i=1; i<=n; ++i)
65         if (!Dfn[i])
66             Tarjan(i);
67     for (int i=1; i<=m; ++i)
68         if (Color[u[i]]!=Color[v[i]])
69             ++Outd[Color[u[i]]];
70 
71     int Ans=0;
72     for (int i=1; i<=Col_num; ++i)
73         if (Outd[i]==0)
74             if (Ans==0)
75                 Ans=Cnt[i];
76             else
77             {
78                 printf("0");
79                 return 0;
80             }
81     printf("%d",Ans);
82 }