lib/graph/reachable_query.hpp

• View this file on GitHub
• Last update: 2024-11-25 23:10:43+09:00
• Include: #include "lib/graph/reachable_query.hpp"

Depends on

• Topological Sort (lib/graph/topological_sort.hpp)

Code

#pragma once

#include "../graph/topological_sort.hpp";

template <typename T>
vector<bool> reachable_query(const vector<vector<T>> &G, const vector<pair<T, T>> &query){
    int n = G.size(), q = query.size();
    vector<T> ord = topological_sort(G);
    vector<bool> res(q);
    for(int l = 0; l < q; l += 64){
        int r = min(q, l + 64);
        vector<long long> dp(n);
        for(int k = l; k < r; k++){
            auto [a, b] = query[k];
            dp[a] |= 1LL << (k - l);
        }
        for(auto &idx : ord){
            for(auto &to : G[idx]){
                dp[to] |= dp[idx];
            }
        }
        for(int k = l; k < r; k++){
            auto [a, b] = query[k];
            res[k] = (dp[b] >> (k - l)) & 1;
        }
    }
    return res;
}

#line 2 "lib/graph/reachable_query.hpp"

#line 2 "lib/graph/topological_sort.hpp"

/**
 * @brief Topological Sort
 * @docs docs/graph/topological_sort.md
 */

#include <vector>
#include <queue>

template <typename T>
std::vector<T> topological_sort(const std::vector<std::vector<T>> &G){
    int siz = (int) G.size();
    std::vector<int> indegree(siz);
    for(int i = 0; i < siz; i++){
        for(auto x : G[i]){
            indegree[x]++;
        }
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for(int i = 0; i < siz; i++){
        if(indegree[i] == 0){
            heap.push(i);
        }
    }

    std::vector<T> res;
    while(!heap.empty()){
        int node = heap.top();
        heap.pop();
        res.push_back(node);
        for(auto x : G[node]){
            indegree[x]--;
            if(indegree[x] == 0){
                heap.push(x);
            }
        }
    }
    return res;
}
#line 4 "lib/graph/reachable_query.hpp"

template <typename T>
vector<bool> reachable_query(const vector<vector<T>> &G, const vector<pair<T, T>> &query){
    int n = G.size(), q = query.size();
    vector<T> ord = topological_sort(G);
    vector<bool> res(q);
    for(int l = 0; l < q; l += 64){
        int r = min(q, l + 64);
        vector<long long> dp(n);
        for(int k = l; k < r; k++){
            auto [a, b] = query[k];
            dp[a] |= 1LL << (k - l);
        }
        for(auto &idx : ord){
            for(auto &to : G[idx]){
                dp[to] |= dp[idx];
            }
        }
        for(int k = l; k < r; k++){
            auto [a, b] = query[k];
            res[k] = (dp[b] >> (k - l)) & 1;
        }
    }
    return res;
}

Back to top page