CSES 1705：Forbidden Cities

CSES 1705：Forbidden Cities

題目大意：給你一張無向圖，有 $q$ 筆詢問，每次給你 $a, b, c$，問你 $a$ 是否可以不經過 $c$ 到達 $b$。

解法：先把點雙連通分量找出來，然後就有一棵樹 (據說叫圓方樹)，這棵樹裡的點是以割點 - 點雙連通分量 - 割點連接的。然後之後就可以 $\text{lca}$ 了。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second
 
const int SIZE = 2e5 + 5;
const int H = __lg (SIZE) + 1;
 
int n, m, q;
vector<int> adj[SIZE];
int dfcnt, bccnt;
int dfn[SIZE], low[SIZE];
vector<int> st, bcc[SIZE];
int id[SIZE];
bool cut[SIZE];
vector<int> tree[SIZE];
int to[SIZE][H + 1], h[SIZE];
 
void tarjan (int pos, int fa) {
    dfn[pos] = low[pos] = ++dfcnt;
    st.pb (pos);
    for (int np : adj[pos]) {
        if (!dfn[np]) {
            tarjan (np, pos);
            low[pos] = min (low[pos], low[np]);
            if (dfn[pos] <= low[np]) {
                bccnt++;
                while (1) {
                    int x = st.back();
                    bcc[x].pb (bccnt);
                    st.pop_back();
                    if (x == np) break;
                }
                bcc[pos].pb (bccnt);
            }
        } else if (np != fa) {
            low[pos] = min (low[pos], dfn[np]);
        }
    }
}
 
void solve() {
    cin >> n >> m >> q;
    FOR (i, 1, m) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
        adj[b].pb (a);
    }
    FOR (i, 1, n) if (!dfn[i]) tarjan (i, i);
    FOR (i, 1, n) {
        if (bcc[i].size() >= 2) {
            id[i] = ++bccnt;
            cut[id[i]] = 1;
            for (int x : bcc[i]) {
                tree[id[i]].pb (x);
                tree[x].pb (id[i]);
            }
        } else {
            id[i] = bcc[i][0];
        }
    }
    n = bccnt;
    function<void (int, int)> build = [&] (int pos, int fa) {
        for (int np : tree[pos]) {
            if (np != fa) {
                h[np] = h[pos] + 1;
                to[np][0] = pos;
                build (np, pos);
            }
        }
    };
    h[1] = 1, build (1, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];
    auto jump = [] (int pos, int k) {
        int cnt = 0;
        while (k) {
            if (k & 1) pos = to[pos][cnt];
            cnt++;
            k >>= 1;
        }
        return pos;
    };
    auto lca = [&] (int a, int b) {
        if (h[a] < h[b]) swap (a, b);
        a = jump (a, h[a] - h[b]);
        if (a == b) return a;
        for (int i = H; i >= 0; i--) {
            if (to[a][i] != to[b][i]) {
                a = to[a][i];
                b = to[b][i];
            }
        }
        return to[a][0];
    };
    while (q--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == c || b == c) {cout << "NO\n"; continue;}
        a = id[a], b = id[b], c = id[c];
        if (!cut[c]) {cout << "YES\n"; continue;}
        int root = lca (a, b);
        if (h[a] >= h[c] && h[c] >= h[root] && jump (a, h[a] - h[c]) == c) {cout << "NO\n"; continue;}
        if (h[b] >= h[c] && h[c] >= h[root] && jump (b, h[b] - h[c]) == c) {cout << "NO\n"; continue;}
        cout << "YES\n";
    }
}
 
int main() {
    Waimai;
    solve();
}

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