読者です 読者をやめる 読者になる 読者になる

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