AOJ 2222 - Alien's Counting

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2222

問題文はそのうち。

解法

強連結成分分解した後木DP。詳しい解説は後でかくかも。

ソースコード

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;

typedef long long ll;

const ll kMOD = 1000 * 1000 * 1000 + 7;
const int kMAX_V = 1010;

struct SCC {
    int V;
    int new_V;
    vector<int> graph[kMAX_V];
    vector<int> rev_graph[kMAX_V];
    vector<int> new_graph[kMAX_V];
    vector<int> vs;
    bool used[kMAX_V];
    int group[kMAX_V];

    SCC() { }

    void Init(int v_num) {
        V = v_num;
    }

    void AddEdge(int from, int to) {
        graph[from].push_back(to);
        rev_graph[to].push_back(from);
    }

    void DFS(int v) {
        used[v] = true;
        for (int i = 0; i < graph[v].size(); i++) {
            int to = graph[v][i];
            if (!used[to]) DFS(to);
        }
        vs.push_back(v);
    }

    void RevDFS(int v, int k) {
        used[v] = true;
        group[v] = k;
        for (int i = 0; i < rev_graph[v].size(); i++) {
            int to = rev_graph[v][i];
            if (!used[to]) RevDFS(to, k);
        }
    }

    // 頂点数と区分を返す
    pair<int, int*> Solve() {
        memset(used, false, sizeof(used));
        vs.clear();
        for (int v = 0; v < V; v++) {
            if (!used[v]) DFS(v);
        }
        memset(used, false, sizeof(used));
        int k = 0;
        for (int i = vs.size() - 1; i >= 0; i--) {
            if (!used[vs[i]]) RevDFS(vs[i], k++);
        }
        new_V = k;
        return make_pair(k, group);
    }

    // 辺を逆に張ったグラフを構築する。頂点はトポロジカル順序になるように番号付けられており、
    // さらにもともと各頂点からは辺が一つしか出ないことがわかっているのでグラフ全体は森として考えることができる。
    // そして頂点番号が大きいノードがそれぞれの木における根である。
    // 簡単のため, 頂点番号が小さいノードが根となるように改めて番号付けをする。
    pair<int, vector<int>*> ConstructNewRevGraph() {
        Solve();
        for (int v = 0; v < V; v++) {
            for (int i = 0; i < graph[v].size(); i++) {
                int to = graph[v][i];
                if (group[v] != group[to]) {
                    // 辺を逆に張る
                    new_graph[new_V - group[to] - 1].push_back(new_V - group[v] - 1);
                }
            }
        }
        return make_pair(new_V, new_graph);
    }
};


SCC scc;

ll dp[kMAX_V][2];
bool used[kMAX_V];
vector<int>* graph;

ll CountWays(int node, int bending) {
    if (dp[node][bending] >= 0) {
        return dp[node][bending];
    }
    used[node] = true;
    ll res = 1;
    for (int i = 0; i < graph[node].size(); i++) {
        int to = graph[node][i];
        ll temp = 0;
        for (int to_bending = 0; to_bending <= 1; to_bending++) {
            if (!bending && to_bending) continue;
            temp = (temp + CountWays(to, to_bending)) % kMOD;
        }
        res = (res * temp) % kMOD;
    }
    return dp[node][bending] = res;
}

int main() {
    int N, M;
    cin >> N >> M;

    scc.Init(N);

    for (int i = 0; i < M; i++) {
        int s, d;
        cin >> s >> d;
        scc.AddEdge(s - 1, d - 1);
    }

    pair<int, vector<int>*> graph_info = scc.ConstructNewRevGraph();
    int V = graph_info.first;
    graph = graph_info.second;

    memset(dp, -1, sizeof(dp));
    ll ans = 1;
    for (int v = 0; v < V; v++) {
        if (!used[v]) {
            ll temp = (CountWays(v, 0) + CountWays(v, 1)) % kMOD;
            ans = (ans * temp) % kMOD;
        }
    }
    cout << ans << endl;

    return 0;
}

感想

解説が雑。