POJ3256 Cow Picnic
強連結成分分解使わなくても適当に探索したら通りそうだけど、強連結成分分解の練習のために縛りプレイを敢行。
バグ取り時間かかった。
#include<stdio.h> #include<algorithm> #include<vector> #include<stack> #include<queue> using namespace std; typedef pair<int,int> pii; vector<int>map[1000]; vector<int>rmp[1000]; int topo[1000]; int used[1000]; int usi[1000]; stack<int>sta; vector<int>gra[1000]; int cit; int kos[1000]; int usis[1000]; int dp[1000]; void dfs(int now) { used[now]=1; for(int i=0;i<map[now].size();i++) { if(used[map[now][i]]==0) { dfs(map[now][i]); } } sta.push(now); } void rdf(int now,int to) { used[now]=1; topo[now]=to; for(int j=0;j<rmp[now].size();j++) { if(used[rmp[now][j]]==0) { rdf(rmp[now][j],to); } } } int scc() { fill(used,used+1000,0); for(int i=0;i<cit;i++) { if(used[i]==0) { dfs(i); } } fill(used,used+1000,0); int now=0; for(int j=0;j<cit;j++) { if(used[sta.top()]==0) { rdf(sta.top(),now); now++; } sta.pop(); } return now; } int main() { fill(topo,topo+1000,0); fill(usi,usi+1000,0); fill(usis,usis+1000,0); fill(dp,dp+1000,0); fill(kos,kos+1000,0); int cow,way; scanf("%d%d%d",&cow,&cit,&way); vector<int>cows; for(int i=0;i<cow;i++) { int zan; scanf("%d",&zan); zan--; cows.push_back(zan); usi[zan]++; } for(int j=0;j<way;j++) { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; map[za].push_back(zb); rmp[zb].push_back(za); } int ren=scc(); for(int k=0;k<cit;k++) { for(int l=0;l<map[k].size();l++) { gra[topo[map[k][l]]].push_back(topo[k]); } kos[topo[k]]++; usis[topo[k]]+=usi[k]; } int hoge=0; for(int q=0;q<ren;q++) { fill(used,used+1000,0); queue<int>que; que.push(q); int retu=0; for(;;) { if(que.empty()) { break; } int zan=que.front(); que.pop(); if(used[zan]==1) { continue; } used[zan]=1; retu+=usis[zan]; for(int s=0;s<gra[zan].size();s++) { if(used[gra[zan][s]]==0) { que.push(gra[zan][s]); } } } if(retu==cow) { hoge+=kos[q]; } } printf("%d\n",hoge); }