Codeforces 118 E. Bertown roads

問題

n頂点m本の辺からなる無向グラフが与えられる。
このグラフの辺に適当な向き付けを与え、有向グラフにして、
全体を強連結（任意の2頂点u,vについてuからvへのパスが存在する）にすることができるか答えよ。

できる場合は具体的な向き付けを一つ出力せよ。

制約条件

n≦2*10^5
m≦3*10^5

方針

元のグラフが二重辺連結になっていればよい。
それはどのように判定するかというと、
まず一度もとのグラフで適当に深さ優先探索して、そのときの辺の向き付けを全て覚えておく。

次にもう一度グラフを深さ優先探索するのだが、このときに、前回と反対向きの辺のみを使って探索する。
これで全ての頂点へ辿り着けたら元のグラフは二重辺連結になっている。

何でだろう……

ソースコード

int n,m;
int v[200000];
vector<vi> g;
map<pi,int> dir;

void dfs(int c){
	v[c]=1;
	rep(i,g[c].size()){
		int to=g[c][i];
		if(!dir.count(mp(c,to))){
			dir[mp(c,to)]=1; dir[mp(to,c)]=0;
			if(!v[to])dfs(to);
		}
	}
}
int  rdfs(int c){
	v[c]=1;
	int res=1;
	rep(i,g[c].size()){
		int to=g[c][i];
		if(dir[mp(c,to)]==0&&!v[to])res+=rdfs(to);
	}
	return res;
}
void run()
{
	cin>>n>>m;
	g.resize(n);
	rep(i,m){
		int a,b; cin>>a>>b;
		g[--a].pb(--b); g[b].pb(a);
	}
	dfs(0);
	memset(v,0,sizeof(v));
	if(rdfs(0)<n){
		cout<<0<<endl; return;
	}
	fr(i,dir)if(i->second)cout<<i->first.first+1<<" "<<i->first.second+1<<endl;
}