CSES 2143：Reachability Queries

CSES 2143：Reachability Queries

題目大意：給你一個有向圖，有多次詢問，問點 $a$ 能不能到點 $b$。

解法：$\text{SCC + bitset}$。

$\text{Code：}$

#pragma GCC opitimize("O3")
#pragma GCC target ("popcnt")
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 5e4 + 5;

int n, m, t;
vector<int> adj[SIZE], st;
int sccnt, dfcnt;
int dfn[SIZE], low[SIZE], scc[SIZE];
bool ist[SIZE];

void tarjan (int pos) {
    dfn[pos] = low[pos] = ++dfcnt;
    st.push_back (pos), ist[pos] = 1;
    for (int np : adj[pos]) {
        if (!dfn[np]) {
            tarjan (np);
            low[pos] = min (low[pos], low[np]);
        } else if (ist[np])
            low[pos] = min (low[pos], low[np]);
    }
    if (dfn[pos] == low[pos]) {
        sccnt++;
        while (1) {
            scc[st.back()] = sccnt;
            ist[st.back()] = 0;
            if (pos == st.back()) {
                st.pop_back();
                break;
            }
            st.pop_back();
        }
    }
}

void solve() {
    cin >> n >> m >> t;
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back (b);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan (i);
    }

    vector<int> scc_adj[sccnt + 1];
    for (int i = 1; i <= n; i++) {
        for (int np : adj[i]) {
            if (scc[i] != scc[np])
                scc_adj[scc[np]].push_back (scc[i]);
        }
    }

    int in[sccnt + 1] = {};
    queue<int> q;
    bitset<SIZE> bs[sccnt + 1];
    for (int i = 1; i <= sccnt; i++) {
        sort (scc_adj[i].begin(), scc_adj[i].end());
        scc_adj[i].erase (unique (scc_adj[i].begin(), scc_adj[i].end()), scc_adj[i].end());
        for (int np : scc_adj[i])
            in[np]++;
    }
    for (int i = 1; i <= sccnt; i++) {
        if (in[i] == 0) {
            q.push (i);
            bs[i].set (i);
        }
    }

    while (!q.empty()) {
        int pos = q.front();
        q.pop();
        for (int np : scc_adj[pos]) {
            bs[np] |= bs[pos];
            in[np]--;
            if (in[np] == 0) {
                q.push (np);
                bs[np].set (np);
            }
        }
    }

    while (t--) {
        int a, b;
        cin >> a >> b;
        cout << (bs[scc[a]][scc[b]] ? "YES\n" : "NO\n");
    }
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！