AtCoder ARC #143 : D - Bridges

この回かかった時間がB＞C＞D＞Eなんだよな…。
https://atcoder.jp/contests/arc143/tasks/arc143_d

問題

1～Nの整数値を取るM要素の数列２つA,Bがある。
以下2N頂点(N+M)辺のグラフを考える。

• 最初のN辺は、i番と(i+N)番の点をつなぐ。
• 残りM辺は、A[i]番と(B[i]+N)番の点をつなぐ辺か、B[i]番と(A[i]+N)番の点をつなぐ辺か、選択できる。

橋の個数が最小となるよう、M辺の選び方を一つ示せ。

解法

N点M辺のグラフを考える。
各辺は、A[i]番とB[i]番の点をつなぐものとする。

各辺に向きを与えることを、元のグラフでどちらの選択をするかに対応付けるとする。
このグラフで橋となる辺は、元のグラフでも橋となる。
そこで、橋を最小化するにはDFS順で向きをつけ、閉路を作るようにすればよい。

int N,M;
int A[202020],B[202020];

set<pair<int,int>> E[202020];
int R[202020];

void dfs(int cur) {
	while(E[cur].size()) {
		auto a=*E[cur].begin();
		E[cur].erase(E[cur].begin());
		int e=a.first;
		int id=a.second;
		if(id<M) {
			R[id]=0;
			E[B[id]].erase({A[id],id+M});
		}
		else {
			R[id-M]=1;
			E[A[id-M]].erase({B[id-M],id-M});
		}
		dfs(e);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i];
		A[i]--;
	}
	FOR(i,M) {
		cin>>B[i];
		B[i]--;
		E[A[i]].insert({B[i],i});
		E[B[i]].insert({A[i],i+M});
	}
	
	FOR(i,N) dfs(i);
	
	FOR(i,M) cout<<R[i];
	cout<<endl;
	
}

まとめ

これはさっと思いつけて良かったね。