AOJ 2222: Alien’s Counting

Any finger appears at most once in S.

を読み落としていてひたすら悩んでいた。

solution

強連結成分分解。でてくるDAGは特に木のようになっているので根から再帰的にやる。$O(N + M \log M)$。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#include <functional>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

vector<vector<int> > opposite_graph(vector<vector<int> > const & g) {
    int n = g.size();
    vector<vector<int> > h(n);
    repeat (i, n) for (int j : g[i]) h[j].push_back(i);
    return h;
}
pair<int, vector<int> > decompose_to_strongly_connected_components(vector<vector<int> > const & g, vector<vector<int> > const & g_rev) {
    int n = g.size();
    vector<int> acc(n); {
        vector<bool> used(n);
        function<void (int)> dfs = [&](int i) {
            used[i] = true;
            for (int j : g[i]) if (not used[j]) dfs(j);
            acc.push_back(i);
        };
        repeat (i,n) if (not used[i]) dfs(i);
        whole(reverse, acc);
    }
    int size = 0;
    vector<int> component_of(n); {
        vector<bool> used(n);
        function<void (int)> rdfs = [&](int i) {
            used[i] = true;
            component_of[i] = size;
            for (int j : g_rev[i]) if (not used[j]) rdfs(j);
        };
        for (int i : acc) if (not used[i]) {
            rdfs(i);
            ++ size;
        }
    }
    return { size, move(component_of) };
}
vector<vector<int> > decomposed_graph(int size, vector<int> const & component_of, vector<vector<int> > const & g) {
    int n = g.size();
    vector<vector<int> > h(size);
    repeat (i, n) for (int j : g[i]) {
        if (component_of[i] != component_of[j]) {
            h[component_of[i]].push_back(component_of[j]);
        }
    }
    repeat (k, size) {
        whole(sort, h[k]);
        h[k].erase(whole(unique, h[k]), h[k].end());
    }
    return h;
}

constexpr int mod = 1e9+7;
int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int s, d; scanf("%d%d", &s, &d); -- s; -- d;
        g[s].push_back(d);
    }
    int size; vector<int> component_of; tie(size, component_of) = decompose_to_strongly_connected_components(g, opposite_graph(g));
    vector<vector<int> > h = decomposed_graph(size, component_of, g);
    vector<vector<int> > h_rev = opposite_graph(h);
    int result = 1;
    function<int (int)> go = [&](int i) {
        int acc = 1;
        for (int j : h_rev[i]) {
            acc = acc *(ll) go(j) % mod;
        }
        return acc + 1;
    };
    repeat (i, size) {
        if (h[i].empty()) {
            result = result *(ll) go(i) % mod;
        }
    }
    printf("%d\n", result);
    return 0;
}