PKU 3660 Cow Contest

http://poj.org/problem?id=3660
n匹の牛がいて、それぞれの牛はことなる実力を持っている。
1対1で戦うとき、実力の高い牛が勝つ。
ここでm個の勝負の情報が与えられる。それぞれの情報はどの牛がどの牛に勝ったかを表している。
この条件のもとで、何匹の牛の強さの順番が特定できるかを求めろというような問題。

グラフを書いて、下のほうと上のほうで全部の牛に辿りつけるとき、その牛の順番は特定できる。

bool vis[100];
vector<int> W[100],S[100];

int udfs(int v){
  vis[v]=true;
  int ret=1;
  rep(i,SZ(W[v])){
    int to=W[v][i];
    if(vis[to])continue;
    ret+=udfs(to);
  }
  return ret;
}

int ddfs(int v){
  vis[v]=true;
  int ret=1;
  rep(i,SZ(S[v])){
    int to=S[v][i];
    if(vis[to])continue;
    ret+=ddfs(to);
  }
  return ret;
}

main(){
  int n,m;
  cin>>n>>m;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    --a,--b;
    W[a].pb(b);
    S[b].pb(a);
  }

  int ans=0;
  rep(i,n){
    memset(vis,0,sizeof(vis));
    int t=1;
    int u,d;
    u=udfs(i)-1;
    d=ddfs(i)-1;
    ans+=t+d+u==n;
  }
  cout<<ans<<endl;
}