洛谷2341 [HAOI2006]受欢迎的牛

题意

有 $N$ 头奶牛，奶牛都喜欢自己，并且有 $M$ 个单向喜欢关系。定义一头被所有奶牛喜欢的奶牛为受欢迎的，求有多少头受欢迎的奶牛。

其中 $N\le 10000,M\le 50000$

题解

把喜欢关系转化为有向图，这样处于同一个强连通分量中的牛肯定是互相喜欢的，那么我们就可以把强连通分量给缩成点。

然后反着考虑，如果一个点出度为 $0$ ，那么其他点就不可能受欢迎，受欢迎的就只有这一个点。这就意味着如果存在受欢迎的奶牛，那它一定在出度为 $0$ 的强连通分量里。

如果有多个点出度为 $0$ ，那么就没有受欢迎的奶牛，输出 $0$ 。

具体做法是 $Tarjan$ 时记录下每个分量包含的点的个数 $siz[]$ ，通过枚举来得到每个分量的出度，最后统计答案即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[50005];
stack <int> s;
bool have_out[10005];
int cnt,n,m,a,b,head[10005];
int scnt,dfsord,id[10005],low[10005],scc[10005],siz[10005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            siz[scnt]++;
            if (x==t) break;
        }
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i);
    }
    for (int x=1;x<=n;x++)
    {
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (scc[x]==scc[y]) continue;
            have_out[scc[x]]=1;
        }
    }
    int ocnt=0,ans=0;
    for (int i=1;i<=scnt;i++)
    {
        if (have_out[i]) continue;
        ocnt++;
        if (ocnt>1) { ans=0; break; }
        else ans=siz[i];
    }
    printf("%d",ans);
    return 0;
}