Popular cattle solution

Description of the topic

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

Cows are narcissistic, and every cow always likes it. The "like" between cows can be passed on - if A

Hua B, B like C, then A also likes C. There are N cows in the cowshed. Given the love relationship between some cows, please

Calculate how many cows can be a star.

Input and output format

Input format:  First line: two integers separated by spaces: N and M

 The second line to the M + 1 line: two lines separated by spaces: A and B, indicating that A likes B

Output format:  The first line: a single integer, indicating the number of star cows

Input and output sample

Enter sample #1: Copy 3 3 1 2 twenty one twenty three Output Sample #1: Copy 1 Description

Only cow 3 can be a star

【data range】

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

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

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

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

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100001;
int begin[maxn],next[maxn],to[maxn];
int tot,n,m;
int dfsn[maxn],low[maxn];
int stack_[maxn];
int num,cc[maxn],dis[maxn];
int put[maxn];
int flag[maxn];
void add_(int x,int y){
    to[++tot]=y;
    next[tot]=begin[x];
    begin[x]=tot;
}

int find_(int x){
    for(register int i=1;i<=stack_[0];++i)
        if(stack_[i]==x)return true;
    return false;
}

void tarjan(int u){
    dfsn[u]=low[u]=++tot;
    stack_[++stack_[0]]=u;
    for(register int i=begin[u];i;i=next[i]){
        int v=to[i];
        if(!dfsn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
            else if(find_(v))low[u]=min(low[u],dfsn[v]);
    }
    if(low[u]==dfsn[u]){
        ++num;
        cc[u]=num;
        while(stack_[stack_[0]]!=u){
            ++dis[num];
            cc[stack_[stack_[0]]]=num;
            --stack_[0];
        }
        ++dis[num];
        cc[stack_[stack_[0]]]=num;
        --stack_[0];    
    }
}

int main(){
    scanf("%d %d",&n,&m);
    register int i,j;
    for(i=1;i<=m;++i){
        int a,b;
        scanf("%d %d",&b,&a);
            add_(a,b);  
    }
    for(i=1;i<=n;++i){
        if(!dfsn[i])tarjan(i);
    }
    for(i=1;i<=n;++i)
        for(j=begin[i];j;j=next[j])
            if(cc[i]!=cc[to[j]])
                ++flag[cc[to[j]]];
    int flag2=0;
    for(i=1;i<=num;++i)
        if(!flag[i])dis[0]=dis[i],++flag2;
    if(flag2>=2)printf("0");
    if(flag2==1)printf("%d",dis[0]);
    return 0;
}