JOI 2009 春合宿 day2-2 「advertisement」
強連結成分分解初めて書いた。(蟻本見ながらだけど)
分解して、どの人からも電話がかかってこない人数を数える。
#include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #define pb push_back using namespace std; vector<int> g[100001], rg[100001], vs, c[100000]; bool used[100001], rused[100001]; int pc[100001], k; void dfs(int v){ used[v] = true; rep(i,g[v].size()){ if(!used[g[v][i]]) dfs(g[v][i]); } vs.pb(v); return; } void rdfs(int v){ rused[v] = true; c[k].pb(v); pc[v] = k; rep(i,rg[v].size()){ if(!rused[rg[v][i]]) rdfs(rg[v][i]); } return; } int main(){ int n, m, a, b, ans = 0; bool bl; scanf("%d%d",&n,&m); rep(i,m){ scanf("%d%d",&a,&b); g[a].pb(b); rg[b].pb(a); } rrep(i,n){ if(!used[i]) dfs(i); } rrep(i,n){ if(!rused[vs[n-i]]){ rdfs(vs[n-i]); k++; } } for(int i = 0; i < n && !c[i].empty(); i++){ bl = true; rep(j,c[i].size()){ rep(h,rg[c[i][j]].size()){ if(pc[rg[c[i][j]][h]] != i) bl = false; } } if(bl) ans++; } printf("%d\n",ans); return 0; }