mayoko’s diary

プロコンとかいろいろ。

AOJ 2222 Alien's Counting


問題

Alien's Counting | Aizu Online Judge

宇宙人に N 本の指があり, この間に M 個の拘束条件が成り立っている。各拘束条件は, 「i 番目の指を曲げたら j 番目の指も自動的に曲がる」と表現される。宇宙人の指の曲げ方は何通りあるか。

解法

明らかに拘束条件が順序関係を持っているように見えるので, SCC して DAG を作ったのち, トポロジカルソートをします。SCC して同じ成分になっているやつは, 「この集合のどれか一つの指を曲げたらすべて曲げることになる」ということを表します。なので, これは一本の指とみなしましょう。

各頂点について, dp[v][0] = (指 v を曲げないような場合の数), dp[v][1] = (指 v を曲げるような場合の数) として, dp します。

dp するとき, 仮想頂点みたいのを一つ作ると楽な気がしました(下の実装はそれをやっていないのでいちいちまだ調べていない頂点を探している)。

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


const int MOD = 1e9+7;
ll dp[1111][2];

ll dfs(int v, int flag, const vector<vi>& g) {
    ll& ret = dp[v][flag];
    if (ret >= 0) return ret;
    if (flag == 0) return ret = 1;
    // v を 1 にする場合
    ret = 1;
    for (int ch : g[v]) {
        ll tmp = dfs(ch, 0, g) + dfs(ch, 1, g);
        (ret *= tmp%MOD) %= MOD;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<vi> G(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[v].push_back(u);
    }
    SCC scc(G);
    int sz = scc.calc();
    vector<vi> g(sz);
    {
        vector<set<int> > S(sz);
        for (int i = 0; i < N; i++) {
            for (int j : G[i]) {
                S[scc.cmp[i]].insert(scc.cmp[j]);
            }
        }
        for (int i = 0; i < sz; i++) {
            for (int j : S[i]) if (j != i) {
                g[i].push_back(j);
            }
        }
    }
    vector<int> order;
    TopologicalSort(g, order);
    memset(dp, -1, sizeof(dp));
    ll ans = 1;
    for (int i = 0; i < sz; i++) {
        int v = order[i];
        if (dp[v][0] == -1) {
            ll tmp = dfs(v, 0, g) + dfs(v, 1, g);
            (ans *= tmp%MOD) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}