WARush

SRMの結果とか、解けた問題のコードを書いていきます

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