MUJINプログラミングチャレンジ : C - オレンジグラフ / Orange Graph

Cまではそこそこ順調。Dが遅れたものの辛うじて解けてギリギリ１ページ目に入った。
http://mujin-pc-2016.contest.atcoder.jp/tasks/mujin_pc_2016_c

問題

N頂点M辺からなるグラフが与えられる。
これらの辺のうち一部の辺に色を塗る。
その際、塗った辺で奇数長の閉路ができないようにしたい。
まだ塗れる辺がある限り、辺を塗る作業を続ける。

最終的な辺の組み合わせとしてあり得る塗り方は何通りか。

解法

奇数長の閉路ができないようにするには、頂点を２グループに分けて２部グラフと見なし、異なるグループ間を結ぶ辺のみ色を塗ればよい。
後は、そのうち全頂点が連結なものだけを数え上げればよい。
頂点のグループの分け方2^(N-1)通りについて、そのような連結判定を行おう。

同じグループの頂点間の辺を塗っても閉路ができないケースもあるが、「全頂点が連結なものだけ～～」の条件により、そのような塗り方を多重にカウントすることを防ぐことができる。

int N,M;
int mat[16][16];

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		mat[x-1][y-1]=mat[y-1][x-1]=1;
	}
	
	int ret=0;
	int mask;
	FOR(mask,1<<N) if(mask&1) {
		UF<32> uf;
		FOR(y,N) FOR(x,y) {
			if((((mask>>x) ^ (mask>>y))&1)==1 && mat[x][y]) uf(x,y);
		}
		if(uf.count(0)==N) ret++;
	}
	
	cout<<ret<<endl;
}

まとめ

本番は連結判定の部分を何も考えず出してしまったが通って良かった。