HNOI2006——受欢迎的牛（强连通分量）

描述
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
输入
第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）
输出
一个数，即有多少头牛被所有的牛认为是受欢迎的。
样例输入
3 3
1 2
2 1
2 3
样例输出
1
提示
数据范围
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000

先tarjan缩点

显然一个强连通分量中如果有一头牛受某头牛欢迎

那么分量中所有牛都是会受它欢迎的

那么只需要缩点之后统计每个点的出度

因为如果只有一个出度为0的点的话，那么这个点中所有牛都是被所以牛欢迎的

考虑如果点$u$u出度不为0，则必定连向了另一个点$v$v

如果点$u$u受所有牛欢迎，则必定有一条$v$v到该点的路径

则必然构成一个环，与已经缩完点的条件不符

而如果有两个出度为0的点，则这两个点一定不相连

则没有牛受欢迎

而如果图不连通

则会存在2个及以上出度为0的点

则答案为0

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
int n,m,adj[10005],nxt[50005],to[50005],vis[10005],dfn[10005],low[10005],bel[10005],belnum,in[10005],num[10006],ans,cnt,tot;
inline void addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
stack<int> stk;
inline void tarjan(int u){
    dfn[u]=low[u]=++tot;
    stk.push(u);
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        belnum++;
        int tmp;
        do{
            tmp=stk.top();;
            stk.pop();
            vis[tmp]=0;
            bel[tmp]=belnum;
            num[belnum]++;
        }while(tmp!=u);
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        addedge(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    for(int u=1;u<=n;u++){
        for(int e=adj[u];e;e=nxt[e]){
            int v=to[e];
            if(bel[u]!=bel[v]){
                in[bel[u]]++;
            }
        }
    }
    int tmp=0;
    for(int i=1;i<=belnum;i++){
        if(!in[i]){
            if(tmp){
                cout<<0;
                return 0;
            }
            tmp=i;
        }
    }
    cout<<num[tmp];
    return 0;
}