mayoko’s diary

プロコンとかいろいろ。

SRM 531 div1 med: MonsterFarm

解法

まず強連結成分分解して, グラフを DAG にします。この DAG において, 終点(その頂点から辺が伸びていないような頂点)への行き方が何通りあるか, というのが, 答えが -1 でない場合の答になります。

これは有名な dp で, トポロジカルソートして後ろから dp していけば良いです。ただ, 今回は答えが無限大になる可能性を考えないといけないので少し面倒です。dp[i] = (i 番目の強連結成分分解から終点にたどり着く場合の数) とすると,

  • 終点で monster が増殖する(i 番目の強連結成分に, 2 本以上辺が伸びている頂点がある)なら, dp[i] = -1
  • それ以外は, 終点では dp[i] = 1(dp[i] = 0 になる可能性があると思われるかもしれませんが, 今回の入力形式ではすべての頂点が 1 本以上辺を伸ばしていることが保証されているので, 0 になることはありえないです)
  • i -> j という辺が存在して, dp[j] = -1 の時は dp[i] = -1
  • 終点でない成分で, u, v が i 番目の強連結成分かつ u -> v への辺が存在するなら, dp[i] = -1(成分 i で monster を増殖させながら終点に monster を常に送り込むことが出来てしまうので)
  • それ以外は dp[i] = sum(dp[j]) (j は i から伸びている辺でたどり着ける成分の集合)

実装でちょっと困ったのは, SCC した成分ごとに DAG を作るところです(これをちゃんとつくらないと Topological Sort が動かない)。これは, set を使って 強連結成分 i から行ける 成分 j を重複させないようにして解決しました。

const int MOD = 1e9+7;

struct SCC {
    int V;
    vector<vi> G, rG;
    vector<int> vs, used, cmp;
    SCC(const vector<vi>& g) : V(g.size()), G(g), rG(V), used(V), cmp(V) {
        for (int i = 0; i < V; i++) for (int u : G[i]) rG[u].push_back(i);
    }
    void dfs(int v) {
        used[v] = 1;
        for (int u : G[v]) if (!used[u]) dfs(u);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = 1;
        cmp[v] = k;
        for (int u : rG[v]) if (!used[u]) rdfs(u, k);
    }
    int calc() {
        fill(used.begin(), used.end(), 0);
        vs.clear();
        for (int v = 0; v < V; v++) {
            if (!used[v]) dfs(v);
        }
        fill(used.begin(), used.end(), 0);
        int k = 0;
        for (int i = vs.size()-1; i >= 0; i--) {
            if (!used[vs[i]]) rdfs(vs[i], k++);
        }
        return k;
    }
};

bool visit(const vector<vi>& g, int v, vector<int>& order, vector<int>& color) {
    color[v] = 1;
    for (int u : g[v]) {
        if (color[u]==2) continue;
        if (color[u]==1) return false;
        if (!visit(g, u, order, color)) return false;
    }
    order.push_back(v); color[v] = 2;
    return true;
}

// トポロジカルソートする
// 返り値が true の時のみ意味を持つ(false の場合は閉路)
bool TopologicalSort(const vector<vi>& g, vector<int>& order) {
    int n = g.size();
    vector<int> color(n);
    for (int u = 0; u < n; u++) if (!color[u] && !visit(g, u, order, color)) return false;
    reverse(order.begin(), order.end());
    return true;
}

class MonsterFarm {
public:
    int numMonsters(vector <string> transforms) {
        int n = transforms.size();
        vector<vi> G(n);
        for (int i = 0; i < n; i++) {
            stringstream ss(transforms[i]);
            int v;
            while (ss>>v) {
                G[i].push_back(v-1);
            }
        }
        SCC scc(G);
        int k = scc.calc();
        vector<vi> Graph(k);
        for (int i = 0; i < n; i++) {
            set<int> S;
            for (int v : G[i]) {
                if (scc.cmp[i] != scc.cmp[v]) S.insert(scc.cmp[v]);
            }
            for (int v : S) {
                Graph[scc.cmp[i]].push_back(v);
            }
        }
        vector<int> order;
        assert(TopologicalSort(Graph, order));
        vector<int> dp(k);
        reverse(order.begin(), order.end());
        vector<vi> comp(k);
        for (int i = 0; i < n; i++) comp[scc.cmp[i]].push_back(i);
        for (int i : order) {
            dp[i] = [&]() {
                if (Graph[i].size() == 0) {
                    // 終点
                    //if (comp[i].size() == 1) return 0;
                    for (int u : comp[i]) {
                        if (G[u].size() > 1) return -1;
                    }
                    return 1;
                } else {
                    int ret = 0;
                    for (int u : comp[i]) {
                        for (int v : G[u]) {
                            if (scc.cmp[v] == scc.cmp[u]) return -1;
                            if (dp[scc.cmp[v]] == -1) return -1;
                            (ret += dp[scc.cmp[v]]) %= MOD;
                        }
                    }
                    return ret;
                }
            }();
        }
        return dp[scc.cmp[0]];
    }
};