SRM566 Div1 Easy - PenguinSledding
問題
n頂点m辺の無向グラフが与えられる
グラフがどんな形になっていても絶対に辺同士が交差しないように辺を削除するとき、最終的なグラフとしてあり得るものは何通りあるか
2 <= n <= 50
1 <= m <= 50
解法
最終的なグラフは
1) 辺が1本もない
2) 辺が1本だけある
3) 辺が2本以上あり、全ての辺が同じ頂点から伸びている
4) 辺が3本あり、それらが三角形になっている
という4パターンに分けられる
それぞれ計算して足し合わせればok
class PenguinSledding { public: ll countDesigns(int n, vector<int> x, vector<int> y) { ll m = x.size(), e[55] = {}, res = m+1; rep(i,m) e[x[i]-1]++, e[y[i]-1]++; rep(i,n) if (e[i]>=2) res += (1ll<<e[i]) - (e[i]+1); int t[55][55] = {}; rep(i,m) t[x[i]-1][y[i]-1] = t[y[i]-1][x[i]-1] = 1; rep(i,n) reps(j,i+1,n) reps(k,j+1,n) if (t[i][j] && t[j][k] && t[k][i]) res++; return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12336&rd=15486