受欢迎的牛 G

题目背景

本题测试数据已修复。

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AA 喜欢 BB，BB 喜欢 CC，那么 AA 也喜欢 CC。牛栏里共有 NN 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：NN 和 MM。

接下来 MM 行：每行两个用空格分开的整数：AA 和 BB，表示 AA 喜欢 BB。

输出格式

一行单独一个整数，表示明星奶牛的数量。

输入输出样例

输入 #1复制

3 3
1 2
2 1
2 3

输出 #1复制

1

说明/提示

只有 33 号奶牛可以做明星。

【数据范围】

对于 10\%10% 的数据，N\le20N≤20，M\le50M≤50。

对于 30\%30% 的数据，N\le10^3N≤103，M\le2\times 10^4M≤2×104。

对于 70\%70% 的数据，N\le5\times 10^3N≤5×103，M\le5\times 10^4M≤5×104。

对于 100\%100% 的数据，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++) //列举这个点的所有邻接点
        {
            if(!D[G[F[i]][j]])
            {
                ans++;   //如果这个点的邻接点不和他在一个强联通分量的话，那么我们就发现他所在的分量有了出度
            }
        }
    }

    return ans;
}//找一组强连通分量的出度
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;
}