bzoj 1051 受欢迎的牛-tarjan

https://www.lydsy.com/JudgeOnline/problem.php?id=1051

如果A喜欢B，那么A->B连边，那么整个图储存下来，如果有好多个牛是受欢迎的，那么他们一定会在一个环中，所以我们先跑一边 tarjan缩点，那么受欢迎的牛群所在的这个点(缩完)，其出度为0。

证：若其出度不为0，则表明对外有连边，因为牛群是受欢迎的则外来点对其也应该有连边，那么他们这就会在一个环中。

所以缩完点后，统计一下每个强联通分量中有多少个点，记录每个点有多少出度，若会存在有两个及以上出度为0的点，那么表明图不连通，则输出0就好了。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn int(1e2+2)

#define N int(1e4+2)

#define M int(5e4+2)

using namespace std;

int n,m,ans[N],sum[N];

struct ahah{

    int nxt,to;

}edge[M];

int head[N],tot;

void add(int x,int y)

{

    edge[++tot].nxt=head[x],edge[tot].to=y,head[x]=tot;

}

bool in[N];

int dfn[N],low[N],indx;

int stack[N],top;

int belong[N],cnt;

void tarjan(int s)

{

    dfn[s]=low[s]=++indx;

    in[s]=,stack[++top]=s;

    for(int i=head[s];i;i=edge[i].nxt)

    {

        int v=edge[i].to;

        if(!dfn[v])

        {

            tarjan(v);

            low[s]=min(low[v],low[s]);

        }

        else if(in[v]&&low[s]>dfn[v])low[s]=dfn[v];

    }

    if(dfn[s]==low[s])

    {

        int p;

        belong[s]=++cnt;

        do

        {

            p=stack[top--];

            in[p]=;

            belong[p]=cnt;

        }while(p!=s);

    }

}

int main()

{

    int x,y;

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);

    for(int i=;i<=n;i++)

        if(!dfn[i])tarjan(i);

    for(int i=;i<=n;i++)

    {

        ans[belong[i]]++;

        for(int j=head[i];j;j=edge[j].nxt)

            if(belong[i]!=belong[edge[j].to])sum[belong[i]]++;

    }

    int p=;

    for(int i=;i<=cnt;i++)

    {

        if(!sum[i])

        {

            if(p)

            {

                printf("");

                return ;

            }

            p=i;

        }

    }

    printf("%d",ans[p]);

}