AtCoder ARC #211 : D - Michishirube

考察はまだしも実装は楽だった。
https://atcoder.jp/contests/arc211/tasks/arc211_d

問題

N点M辺の連結無向グラフが与えられる。
各点に対し、辺を２個選んでその向きに黄色と青の標をつける。

以下を満たすような標の付け方が可能なら一例を示せ。

• どの点からでも、黄色い標の向きに移動を繰り返すと頂点1にたどり着く
• どの点からでも、青い標の向きに移動を繰り返すと頂点2にたどり着く

解法

まず以下頂点1からDFS木を作り、親向きに黄色い標を振ろう。
そのうえで、元のグラフを有向グラフをみなし、黄色い標の向きの辺を削除する。
この上で頂点2から、残った有向辺の向きを逆にしたものに対し再度DFS木を作り、親向きに青い標を振ればよい。

int N,M;
int U[302020],V[302020];
vector<int> E[202020];

int Y[202020],B[202020];

void dfs(int cur,int pre) {
	if(B[cur]!=-1) return;
	B[cur]=pre;
	FORR(e,E[cur]) dfs(e,cur);
}
void dfs2(int cur,int pre) {
	if(Y[cur]!=-1) return;
	Y[cur]=pre;
	FORR(e,E[cur]) dfs2(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i];
		U[i]--;
		V[i]--;
		E[U[i]].push_back(V[i]);
		E[V[i]].push_back(U[i]);
	}
	
	MINUS(B);
	MINUS(Y);
	dfs(0,0);
	FOR(i,N) E[i].clear();
	FOR(i,M) {
		if(U[i]==0||B[U[i]]!=V[i]) E[V[i]].push_back(U[i]);
		if(V[i]==0||B[V[i]]!=U[i]) E[U[i]].push_back(V[i]);
	}
	dfs2(1,1);
	FOR(i,N) if(Y[i]==-1) {
		cout<<"No"<<endl;
		return;
	}
	cout<<"Yes"<<endl;
	cout<<Y[0]+1<<endl;
	cout<<B[1]+1<<endl;
	for(i=2;i<N;i++) {
		cout<<B[i]+1<<" "<<Y[i]+1<<endl;
	}
		
}

まとめ

考察中無駄に二重辺連結成分分解とかしてしまった。