TopCoder SRM 322 Div1 Medium ExtendedDominoes

問題

二つの異なる数字が書かれたドミノがいくつかある。
このドミノを全て使って、全体がちょうどいくつかの輪になるように並べる。

ドミノが輪になっているとは、
左右に隣合うドミノの、隣り合う側の数字がすべて等しく、
かつ、最初のドミノと最後のドミノの両端が等しい数字になっていることを言う。

使うべきドミノが与えられたとき、
ドミノの並べ方は何通りあるか求めよ。
つながっているドミノ同士の関係が同じような並べ方は、同一の並べ方と数えるものとする。

制約条件

ドミノは全て異なる
ドミノに書かれている数字は左右で異なる。
ドミノに書かれている数字は1〜9

方針

1〜9までの数字を頂点として、
abの数字が書かれたドミノが存在するときaとbの間に辺を張ったようなグラフを考える。

このグラフで、全ての頂点の次数が偶数であることは、輪を作れる必要十分条件。
なので作れない場合は0通りにする。

作れる場合、各頂点で、次数をmとすると、
最初に1本の辺から入ってきたときに、出る辺がm-1通りあり、
次に入ってきたときにm-3通りあり、
となって、(m-1) * (m-3) * ... * 1通りその頂点でのグラフの作り方がある。

これを全部の頂点について掛けあわせれば、全体の場合の数が求まる。

ソースコード

class ExtendedDominoes {
	public:
	long long countCycles(vector <string> pieces) 
	{
		int deg[10] = {};
		rep(i, pieces.size()) rep(j, 2) deg[pieces[i][j] - '0']++;
		rep(i, 10) if(deg[i] % 2) return 0;
		
		ll ans = 1;
		rep(i, 10){
			for(; deg[i]; deg[i] -= 2)
				ans = ans * (deg[i] - 1);
		}
		return ans;
	}
};