SRM628 Div2 Hard "InvariantSets"
考えたこと
頂点iを使用するには頂点f[i]は必ず使用しなければならないので、頂点iを含んだサブセットの数え上げは頂点f[i]とは独立して計算することができる。そこで、f[i] -> iというパスがあるグラフを作成してdfsで答えを求めたいところだが、このグラフは閉路ができてしまう場合がある。
閉路になっているということは、そこに含まれる頂点は互いに依存するため、「全てを使う」か「全てを使わない」かのどちらかしか選べないことになる。そのため、それらの頂点は1つの頂点として扱うことができる。ということで、強連結成分分解をしてDAGにする。
あとは、「この頂点をルートとしたときのサブツリーで、頂点のサブセットが何パターンできるか?」をdfsで求めていけばよい。
ソースコード
vector<int> F; int N; bool exist[55]; class InvariantSets { public: long long countSets(vector <int> f) { F = f; N = F.size(); // 閉路を潰す memset(exist, true, sizeof(exist)); for (int i = 0; i < N; i++) { if (exist[i]) { dfs1(i, i); } } // 木のルートを仮想の親ノードの子とする for (int i = 0; i < N; i++) { if (F[i] == i) { F[i] = N; } } // dfsでパターンを求める return dfs2(N) - 1; } int dfs1(int v, int tar) { for (int i = 0; i < N; i++) { if (F[i] != v || i == v) continue; if (i == tar || dfs1(i, tar) == tar) { for (int i = 0; i < N; i++) { if (F[i] != v)continue; F[i] = tar; } if (v != tar) exist[v] = false; return tar; } } return -1; } long long dfs2(int v) { long long res = 1; for (int i = 0; i < N; i++) { if (F[i] != v || i == v || !exist[i]) continue; res *= dfs2(i); } return res + 1; } };