Topic Description

Every cow dreams of becoming a star in the cowshed. A cow loved by all cows is a star cow. All milk

Cows are narcissists. Every cow likes itself. The "likes" between cows can be transmitted - if A likes

Huan B, B likes C, so A likes C. There are N cows in the cattle pen. Given the love relationship between some cows, please.

Figure out how many cows can be stars.

Input and output format

Input format:

Line 1: Two integers separated by spaces: N and M

Lines 2 to M + 1: Two integers separated by spaces in each line: A and B, indicating that A likes B

Output format:

Line 1: A single integer representing the number of star cows

Input and Output Samples

3 3
1 2
2 1
2 3

1

Explain

Only Cow No. 3 can be a star.

[Data Scope]

10% data N<=20, M<=50

30% data N<=1000, M<=20000

70% data N<=5000, M<=50000

100% data N<=10000, M<=50000

tarjan contraction point,

When the outgoing of a point is zero, they are stars.

When two or more stores go to zero, they can't like each other, so there are no stars.

Here's a little trick.

When we add the edge in the opposite direction, we change the problem of finding the degree to that of finding the degree of entry.

  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])// Public Ancestors 
 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 }