TopCoder SRM 685 Div1 Medium FoxAirline2

解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14194

問題

N頂点M辺からなる無向グラフが与えられる。
各辺は自己ループになることはない。
一方同じ頂点対を結ぶ辺が2本以上ある場合がある。

これらの辺を2色に塗り分けたとき、両方の色に対してそれぞれの色の辺だけからなる全域木を構築できるような塗り分けが存在するか判定せよ。

解法

2つの全域木を管理するため、Union-Findのデータ構造を2つ持って、DFSを行い各辺をどちらの色に塗り分けるか求める。

DFSで辺を順に見ていくとき、両方のUnion-Findデータに対して、その辺を用いて新規に頂点を連結できるかどうかを判定していく。

• 両色どちらもその辺で新規に連結できるなら、両方を試す。
• そうでない場合(どちらかの色で、その辺でつなぐ元々2頂点が連結済みである場合)、まだ連結されてない方にその辺を割り当てる。

最終的に両方のUnion-Findデータがそれぞれ全部連結出来れば、問題の条件を満たす。

Nが10以下なので、両色とも9本辺があれば全域木を作れる。
そのため、「両色で新規に連結できるなら、両方を試す。」というケースは高々9回しか生じないので、DFSの分岐は2^9通りで収まる。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int A[51],B[51];

class FoxAirline2 {
	public:
	int N,M;
	int ok;
	
	void dfs(int cur,UF<10>& uf1,UF<10>& uf2) {
		if(cur==M) {
			if(uf1.count(0)==N && uf2.count(0)==N) ok=1;
			return;
		}
		
		if(uf1[A[cur]]!=uf1[B[cur]]) {
			UF<10> ufa=uf1;
			ufa(A[cur],B[cur]);
			dfs(cur+1,ufa,uf2);
		}
		if(uf2[A[cur]]!=uf2[B[cur]]) {
			UF<10> ufa=uf2;
			ufa(A[cur],B[cur]);
			dfs(cur+1,uf1,ufa);
		}
		if(uf1[A[cur]]==uf1[B[cur]] && uf2[A[cur]]==uf2[B[cur]]) dfs(cur+1,uf1,uf2);
	}
	
	string isPossible(int n, vector <int> a, vector <int> b) {
		int i;
		N=n;
		M=a.size();
		FOR(i,M) A[i]=a[i],B[i]=b[i];
		UF<10> uf1,uf2;
		ok=0;
		dfs(0,uf1,uf2);
		if(ok) return "Possible";
		else return "Impossible";
	}
}

まとめ

Mは大きいのでO(2^M)かかる方法は取れないけど、O(2^N)なら間に合うことを用いると簡単。