每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你
算出有多少头奶牛可以当明星。
输入格式:
第一行:两个用空格分开的整数:N和M
第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B
输出格式:
第一行:单独一个整数,表示明星奶牛的数量
输入样例#1:
3 3
1 2
2 1
2 3
输出样例#1:
1
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
tarjan缩点,
当一个点的出度为0是,他们是明星、
当有两个及以上的店出度为0是,他们不可能相互喜欢,所以没有明星。
这里有个小技巧,
我们反向加边,就把求出度的问题改为了求入度的问题
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 #include<stack>
8 using namespace std;
9 const int MAXN=500001;
10 static void read(int &n)
11 {
12 char c='+';int x=0;bool flag=0;
13 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14 while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 struct node
18 {
19 int u,v,nxt;
20 }edge[MAXN];
21 int head[MAXN];
22 int num=1;
23 void add_edge(int x,int y)
24 {
25 edge[num].u=x;
26 edge[num].v=y;
27 edge[num].nxt=head[x];
28 head[x]=num++;
29 }
30 int dfn[MAXN];
31 int low[MAXN];
32 int tot=0;
33 int vis[MAXN];
34 int color[MAXN];
35 int colornum;
36 int happen[MAXN];
37 stack<int>s;
38 void tarjan(int now)
39 {
40 dfn[now]=low[now]=++tot;
41 vis[now]=1;
42 s.push(now);
43 for(int i=head[now];i!=-1;i=edge[i].nxt)
44 {
45 if(!dfn[edge[i].v])
46 {
47 tarjan(edge[i].v);
48 low[now]=min(low[now],low[edge[i].v]);
49 }
50 else if(vis[edge[i].v])// 公共祖先
51 {
52 low[now]=min(low[now],dfn[edge[i].v]);
53 }
54 }
55 if(dfn[now]==low[now])// root
56 {
57 colornum++;
58 while(now!=s.top())
59 {
60 if(!color[s.top()])
61 color[s.top()]=colornum;
62 happen[color[s.top()]]++;
63 vis[s.top()]=0;
64 s.pop();
65 }
66 if(!color[s.top()])
67 color[s.top()]=colornum;
68 happen[color[s.top()]]++;
69 vis[s.top()]=0;
70 s.pop();
71 }
72 }
73 int main()
74 {
75 // freopen("cow.in","r",stdin);
76 // freopen("cow.out","w",stdout);
77 int n,m;
78 memset(head,-1,sizeof(head));
79 read(n);read(m);
80 for(int i=1;i<=m;i++)
81 {
82 int x,y;
83 read(x);read(y);
84 add_edge(y,x);
85 }
86
87 for(int i=1;i<=n;i++)
88 if(!dfn[i])
89 tarjan(i);
90 // for(int i=1;i<=n;i++)
91 // happen[color[i]]++;
92 memset(vis,0,sizeof(vis));
93 for(int i=1;i<=n;i++)
94 for(int j=head[i];j!=-1;j=edge[j].nxt)
95 if(color[edge[j].u]!=color[edge[j].v])
96 vis[color[edge[j].v]]++;
97 int ans=0;
98 for(int i=1;i<=colornum;i++)
99 if(!vis[i])
100 {
101 if(ans)
102 {
103 printf("0\n");
104 return 0;
105 }
106 else ans=happen[i];
107 }
108 printf("%d",ans);
109 return 0;
110 }