Block cut tree (Biconnected component)

BCC.cpp

// https://cses.fi/problemset/result/7855807/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class BinaryLifting {
    vector<vector<ll>> graph;
    vector<vector<ll>> parent;
    vector<ll> depth;
    ll MAXLOG;

    void _dfs(ll u, ll p, ll d) {
        parent[u][0] = p;
        depth[u] = d;

        for (ll i : graph[u]) {
            if (i == p) {
                continue;
            }

            _dfs(i, u, d + 1);
        }
    }

   public:
    BinaryLifting() {}

    BinaryLifting(vector<vector<ll>>& a, ll root = 1, ll maxLog = 18) {
        graph = a;
        parent = vector<vector<ll>>(graph.size(), vector<ll>(maxLog + 1));
        depth = vector<ll>(graph.size());
        MAXLOG = maxLog;

        _dfs(root, 0, 0);

        for (ll k = 1; k <= maxLog; k++) {
            for (ll i = 1; i < graph.size(); i++) {
                parent[i][k] = parent[parent[i][k - 1]][k - 1];
            }
        }
    }

    ll jump(ll u, ll k) {
        bitset<32> mask(k);

        for (ll i = 0; i <= MAXLOG; i++) {
            if (mask[i]) {
                u = parent[u][i];
            }
        }

        return u;
    }

    ll lca(ll a, ll b) {
        if (depth[a] > depth[b]) {
            swap(a, b);
        }

        b = jump(b, depth[b] - depth[a]);

        if (a == b) {
            return a;
        }

        for (ll i = MAXLOG; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }

        return parent[a][0];
    }

    bool onPath(ll a, ll b, ll c) {
        ll x = lca(a, b), y = lca(a, c), z = lca(b, c);

        return x == c || (x == y && z == c) || (x == z && y == c);
    }
};

class BlockCutTree {
    vector<bool> isJoint;
    vector<ll> in, low, ids;
    vector<vector<ll>> graph, tree, comp;
    BinaryLifting bl;
    ll id = 0;

    void _dfs(stack<ll>& st, ll u, ll p, ll& t) {
        in[u] = low[u] = t++;
        st.push(u);

        for (ll i : graph[u]) {
            if (i == p) {
                continue;
            }

            if (in[i]) {
                low[u] = min(low[u], in[i]);
                continue;
            }

            _dfs(st, i, u, t);

            low[u] = min(low[u], low[i]);

            if (low[i] >= in[u]) {
                isJoint[u] = (in[u] > 1 || in[i] > 2);

                comp.push_back({u});

                while (comp.back().back() != i) {
                    comp.back().push_back(st.top());
                    st.pop();
                }
            }
        }
    }

   public:
    BlockCutTree(vector<vector<ll>> a) {
        graph = a;
        tree = {{}};
        isJoint = vector<bool>(graph.size());
        in = low = ids = vector<ll>(graph.size());

        ll t = 1;
        stack<ll> st;

        _dfs(st, 1, 0, t);

        ll id = 0;

        for (ll i = 1; i < graph.size(); i++) {
            if (isJoint[i]) {
                ids[i] = id++;
                tree.push_back({});
            }
        }

        for (auto& i : comp) {
            for (ll j : i) {
                if (isJoint[j]) {
                    tree[id].push_back(ids[j]);
                    tree[ids[j]].push_back(id);
                } else {
                    ids[j] = id;
                }
            }

            id++;
            tree.push_back({});
        }

        bl = BinaryLifting(tree, 0);
    }

    bool query(ll a, ll b, ll c) {
        if (!isJoint[c]) {
            return true;
        }

        return !bl.onPath(ids[a], ids[b], ids[c]);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    ll n, m, q;
    cin >> n >> m >> q;

    vector<vector<ll>> graph(n + 1);

    while (m--) {
        ll u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    BlockCutTree tree(graph);

    while (q--) {
        ll a, b, c;
        cin >> a >> b >> c;

        if (a == c || b == c) {
            cout << "NO" << '\n';
            continue;
        }

        cout << (tree.query(a, b, c) ? "YES" : "NO") << '\n';
    }
}