TopCoder SRM 566 Div1 Easy PenguinSledding

問題

滑り台とは、座標平面上のn個の支点と、m本のパスであって、
パスは、異なる二つの支点をつないだ線分である。

滑り台のパスは交差していてはならない。

今、支点の数nと、支点と支点をつなぐパスm本が与えられる。
このパスのうち、いくつかを取り除いて、
支点が座標平面上のどの位置にあっても、パスが交差しないようにしたい。

パスの取り除き方は何通りあるか、求めよ。

制約条件

n≦50
m≦50

方針

滑り台の条件について考える。
長さ3以上の閉じていないパスがあったら、それは交差を作れるのでダメ。
また、互いに交わらない線分が2本あったら、それも交差を作れるのでダメ。

つまり、すべてのパスが連結で、長さが2以下であるか、
もしくは、パスがひとつの三角形なす場合のみが滑り台の条件を満たす。

長さが2以下の場合、一点からパスが伸びる形になるので、
始点をひとつ決めることで数え上げることができる。

ソースコード

class PenguinSledding {
	public:
	long long countDesigns(int n, vector <int> checkpoint1, vector <int> checkpoint2) {
		vector<vi> e(n);
		bool g[50][50] = {};
		rep(i, checkpoint1.size()){
			int a = checkpoint1[i], b = checkpoint2[i];
			a--; b--;
			e[a].pb(b);
			e[b].pb(a);
			g[a][b] = g[b][a] = 1;
		}
		
		//パス0本の場合が1通り、パス1本のみの場合がm通り
		ll ans = 1 + checkpoint1.size();
		rep(i, n) {
			ll t = e[i].size();
			if(t <= 1) continue;

			//2^t通りのうち、1本だけ、0本の場合は最初に数えてある
			ans += 1ll << t;
			ans -= t + 1;
		}
		//三角形
		rep(i, n) rep(j, i) rep(k, j){
			if(g[i][j] && g[j][k] && g[k][i]) ans++;
		}
		return ans;
	}
};