任意有向图求传递闭包。Tarjan SCC + bitset 优化。

transitive-closure-Tarjan-SCC-bitset.cpp

const int nax = 10005;
vector<int> g[nax];

int scc_id[nax];
int dn[nax]; // dfs_no
int dfs_clock;
int low[nax];
bitset<nax> bs[nax];
vector<bool> in_stack(nax);
stack<int> stk;
int scc_cnt;

void dfs(int u) {
    dn[u] = low[u] = ++dfs_clock;
    stk.push(u); in_stack[u] = true;
    FOR (v, g[u]) {
        if (!dn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stack[v]) {
            low[u] = min(low[u], dn[v]);
        }
    }
    if (low[u] == dn[u]) {
        while (true) {
            int v = stk.top(); stk.pop(); in_stack[v] = false;
            scc_id[v] = scc_cnt;
            bs[scc_cnt].set(v);
            FOR (x, g[v]) {
                if (scc_id[x] != scc_cnt) {
                    bs[scc_cnt] |= bs[scc_id[x]];
                }
            }
            if (v == u) break;
        }
        ++scc_cnt;
    }
}

void get_scc(int n) {
    for (int i = 1; i <= n; ++i) {
        if (!dn[i]) dfs(i);
    }
}