Directed Graph Reachability
(graph/others/GraphReachability.hpp)

• View this file on GitHub
• Last update: 2024-12-07 20:14:42+09:00
• Include: #include "graph/others/GraphReachability.hpp"

概要

todo

計算量

todo

Depends on

• Strongly Connected Components (graph/connected-components/StronglyConnectedComponents.hpp)

Code

#include "../connected-components/StronglyConnectedComponents.hpp"
class GraphReachability {
   private:
    vector<vector<int>> r;
    queue<pair<int, int>> q;
    vector<int> compress_id;
    SCC s;
    int n;

   public:
    GraphReachability(const vector<vector<int>> &v) {
        int siz = v.size();
        s = SCC(siz);
        compress_id.resize(siz);
        for (int i = 0; i < siz; i++) {
            for (auto j : v[i]) {
                s.add_edge(i, j);
            }
        }

        vector<vector<int>> components = s.decompose();
        for (int i = 0; i < components.size(); i++) {
            for (int idx : components[i]) {
                compress_id[idx] = i;
            }
        }

        n = components.size();
        r.resize(n);

        for (int i = 0; i < siz; i++) {
            for (auto j : v[i]) {
                if (compress_id[i] != compress_id[j]) {
                    r[compress_id[j]].emplace_back(compress_id[i]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            sort(r[i].begin(), r[i].end());
            r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end());
        }
    }

    void is_reachable(int from, int to) {
        q.emplace(from, to);
    }

    vector<bool> build() {
        vector<bool> res(int(q.size()));
        int res_idx = 0;
        int cnt = 0;
        vector<bitset<2048>> dp(n);
        vector<int> goal(2048);

        while (!q.empty()) {
            int a = compress_id[q.front().first];
            int b = compress_id[q.front().second];
            q.pop();
            dp[a].set(cnt);
            goal[cnt] = b;
            cnt++;
            if (cnt == 2048 or q.empty()) {
                for (int i = 0; i < n; i++) {
                    for (int prev : r[i]) {
                        dp[i] |= dp[prev];
                    }
                }
                for (int i = 0; i < cnt; i++) {
                    if (dp[goal[i]][i]) {
                        res[res_idx] = true;
                    } else {
                        res[res_idx] = false;
                    }
                    res_idx++;
                }

                for (int i = 0; i < n; i++) {
                    dp[i].reset();
                }
                cnt = 0;
            }
        }

        return res;
    }
};

#line 1 "graph/connected-components/StronglyConnectedComponents.hpp"

class SCC {
   private:
    vector<vector<int>> g, r;
    int time;
    int n;
    vector<bool> seen, seen2;
    vector<int> idx;
    int component_id;
    vector<vector<int>> components;

    void dfs(int cur) {
        seen[cur] = true;
        for (auto nex : g[cur]) {
            if (seen[nex] == false) {
                dfs(nex);
            }
        }
        idx[time] = cur;
        time++;
    }

    void dfs2(int cur) {
        seen2[cur] = true;
        components[component_id].emplace_back(cur);
        for (auto nex : r[cur]) {
            if (seen2[nex] == false) {
                dfs2(nex);
            }
        }
    }

   public:
    SCC() {}
    SCC(int siz) {
        n = siz;
        g.resize(n);
        r.resize(n);
        time = 0;
        component_id = 0;
        idx.assign(n, -1);
        seen.assign(n, false);
        seen2.assign(n, false);
    }

    void add_edge(int u, int v) {
        g[u].emplace_back(v);
        r[v].emplace_back(u);
    }

    vector<vector<int>> decompose() {
        for (int i = 0; i < n; i++) {
            if (!seen[i]) {
                dfs(i);
            }
        }

        for (int i = time - 1; i >= 0; i--) {
            if (!seen2[idx[i]]) {
                components.emplace_back(vector<int>());
                dfs2(idx[i]);
                component_id++;
            }
        }

        return components;
    }
};
#line 2 "graph/others/GraphReachability.hpp"
class GraphReachability {
   private:
    vector<vector<int>> r;
    queue<pair<int, int>> q;
    vector<int> compress_id;
    SCC s;
    int n;

   public:
    GraphReachability(const vector<vector<int>> &v) {
        int siz = v.size();
        s = SCC(siz);
        compress_id.resize(siz);
        for (int i = 0; i < siz; i++) {
            for (auto j : v[i]) {
                s.add_edge(i, j);
            }
        }

        vector<vector<int>> components = s.decompose();
        for (int i = 0; i < components.size(); i++) {
            for (int idx : components[i]) {
                compress_id[idx] = i;
            }
        }

        n = components.size();
        r.resize(n);

        for (int i = 0; i < siz; i++) {
            for (auto j : v[i]) {
                if (compress_id[i] != compress_id[j]) {
                    r[compress_id[j]].emplace_back(compress_id[i]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            sort(r[i].begin(), r[i].end());
            r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end());
        }
    }

    void is_reachable(int from, int to) {
        q.emplace(from, to);
    }

    vector<bool> build() {
        vector<bool> res(int(q.size()));
        int res_idx = 0;
        int cnt = 0;
        vector<bitset<2048>> dp(n);
        vector<int> goal(2048);

        while (!q.empty()) {
            int a = compress_id[q.front().first];
            int b = compress_id[q.front().second];
            q.pop();
            dp[a].set(cnt);
            goal[cnt] = b;
            cnt++;
            if (cnt == 2048 or q.empty()) {
                for (int i = 0; i < n; i++) {
                    for (int prev : r[i]) {
                        dp[i] |= dp[prev];
                    }
                }
                for (int i = 0; i < cnt; i++) {
                    if (dp[goal[i]][i]) {
                        res[res_idx] = true;
                    } else {
                        res[res_idx] = false;
                    }
                    res_idx++;
                }

                for (int i = 0; i < n; i++) {
                    dp[i].reset();
                }
                cnt = 0;
            }
        }

        return res;
    }
};

Back to top page