PKU 3256 Cow Picnic
http://poj.org/problem?id=3256
n個のノードのどこかに全部でk匹の牛がいて、m個の有向辺がはられている。
このとき、すべての牛から到達可能なノードの個数を求めるという問題。
各ノードにはたかだか一匹の牛しかいないと、勘違いしてWA。
紛らわしい。
int app[1000]; bool vis[1000]; int visnum; vector<int> G[1000]; void dfs(int v){ vis[v]=true; visnum+=app[v]; rep(i,SZ(G[v])){ if(vis[G[v][i]])continue; dfs(G[v][i]); } } main(){ int k,n,m; cin>>k>>n>>m; rep(i,k){ int t; cin>>t; ++app[t-1]; } rep(i,m){ int a,b; cin>>a>>b; G[b-1].pb(a-1); } int ans=0; rep(i,n){ memset(vis,0,sizeof(vis)); visnum=0; dfs(i); if(visnum==k)++ans; } cout<<ans<<endl; }