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; }