Popular cow G

Background

The test data has been fixed .

Title Description

Every cow dreams of being a star in the cowshed . The cow that all cows like is a star cow . All cows are narcissists , Every cow always likes its own . Between cows “ like ” It can be transmitted —— If  AA  like  BB,BB  like  CC, that  AA  I also like  CC. It's in the bullpen  NN  A cow , Given some of the relationships between cows , Please figure out how many cows can be stars .

Input format

first line ： Two integers separated by spaces ：NN  and  MM.

Next  MM  That's ok ： Two integers separated by spaces on each line ：AA  and  BB, Express  AA  like  BB.

Output format

A single integer in a row , The number of star cows .

I/o sample

Input #1 Copy

3 3
1 2
2 1
2 3

Output #1 Copy

1

explain / Tips

Only  33  Cow number one can be a star .

【 Data range 】

about  10\%10%  The data of ,N\le20N≤20,M\le50M≤50.

about  30\%30%  The data of ,N\le10^3N≤103,M\le2\times 10^4M≤2×104.

about  70\%70%  The data of ,N\le5\times 10^3N≤5×103,M\le5\times 10^4M≤5×104.

about  100\%100%  The data of ,1\le N\le10^41≤N≤104,1\le M\le5\times 10^41≤M≤5×104.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int>G[N];
int n,m;
int sum,low[N],ins[N],dfn[N],col,a,cmpi[N],F[N],cmp[N];
bool D[N];
stack<int>s;
int find()
{
    int ans=0;
    for(int i=1; i<=a; i++)
    {
        for(int j=0; j<G[F[i]].size(); j++) // List all adjacent points of this point 
        {
            if(!D[G[F[i]][j]])
            {
                ans++;   // If the adjacent point of this point is not in a strong connection with it , Then we will find that his weight has a degree 
            }
        }
    }

    return ans;
}// Find out the degree of a group of strongly connected components 
void tarjan(int x)
{
    sum++;
    dfn[x]=low[x]=sum;
    s.push(x);
    ins[x]=1;
    for(int i=0; i<G[x].size(); i++)
    {
        if(ins[G[x][i]]==0)
        {
            tarjan(G[x][i]);
            low[x]=min(low[x],low[G[x][i]]);
        }
        else if(ins[G[x][i]]==1)
            low[x]=min(low[x],dfn[G[x][i]]);
    }
    if(dfn[x]==low[x])
    {
        col++;
        int node;
        do
        {
            node=s.top();
            s.pop();
            ins[node]=-1;
            D[node]=true;
            F[++a]=node;
            cmpi[col]++;
        }
        while(node!=x);
        cmp[col]=find();
        a=0;
        memset(D,false,sizeof D);
    }
    return ;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
    }
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i])tarjan(i);
    }
    int c=0,ans;
    for(int i=1; i<=col; i++)
    {
        if(!cmp[i])
        {
            c++,ans=i;
        }
    }
    if(c==1)
    {
        cout<<cmpi[ans];
    }
    else
    {
        cout<<0;
    }

    return 0;
}