HAOI2006 受欢迎的牛

题目:

  每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

思路:

  根据题意可以确定符合要求的牛必须要所有点都能到达它,所以可以对这幅图进行缩点,如果最后有且只有一个块的出度以为0,那么答案就是块的大小。否则答案为0。

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#define MN 10005
#define clr(a,b) memset(a,b,sizeof a)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,50005,int> G,M;
int dfn[MN],low[MN],ble[MN],siz[MN],No,bcnt,stk[MN],tp;
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    EOR(k,G,o){
        int v=G[k];
        if(!dfn[v]){
            dfs(v);
            tomin(low[o],low[v]);
        }
        else if(!ble[v])tomin(low[o],dfn[v]);
    }
    if(dfn[o]==low[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            siz[bcnt]++;
        }while(stk[tp--]!=o);
    }
}
int n;
bool ok[MN];
void rebuild(){
    clr(ok,true);
    for(int i=1;i<=n;i++)
        EOR(k,G,i)
            if(ble[i]!=ble[G[k]])
                ok[ble[i]]=false;
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<=m;i++){
        scanf("%d%d",&a,&b);
        G.add(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!ble[i])dfs(i);
    rebuild();
    int ans=0;
    for(int i=1;i<=bcnt;i++){
        if(ok[i]){
            if(!ans)ans=siz[i];
            else {
                puts("0");
                return 0;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}