cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: graph/test/strongly_connected_components_bitset.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"
#include "../strongly_connected_components_bitset.hpp"
#include <cassert>
#include <stdio.h>

constexpr int VMAX = 10000;
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    assert(V <= VMAX);
    std::vector<std::bitset<VMAX>> e(V), einv(V);
    while (E--) {
        int s, t;
        scanf("%d %d", &s, &t);
        e[s][t] = einv[t][s] = 1;
    }
    DirectedGraphSCC64<VMAX> graph(e, einv);

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", graph.cmp[u] == graph.cmp[v]);
    }
}
#line 1 "graph/test/strongly_connected_components_bitset.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"
#line 2 "graph/strongly_connected_components_bitset.hpp"
#include <bitset>
#include <iostream>
#include <vector>

// CUT begin
// Directed graph library to find strongly connected components （強連結成分分解）
// 0-indexed directed graph
// - using std::bitset
// - Fast for dense graphs
// Complexity: O(V^2/64)
// Verified: CF1268D <https://codeforces.com/contest/1268/submission/68125495>
template <int VMAX> struct DirectedGraphSCC64 {
    int V;
    const std::vector<std::bitset<VMAX>> &e, &einv;
    std::vector<int> vs, cmp;
    std::bitset<VMAX> unvisited;
    int scc_num;
    std::vector<int> _st;

    void _dfs(int head) {
        _st = {head};
        unvisited.reset(head);
        while (!_st.empty()) {
            int now = _st.back();
            unvisited.reset(now);
            int nxt = (unvisited & e[now])._Find_first();
            if (nxt < V) {
                unvisited.reset(nxt);
                _st.push_back(nxt);
            } else {
                _st.pop_back();
                vs.push_back(now);
            }
        }
    }

    void _rdfs(int head, int k) {
        _st = {head};
        unvisited.reset(head);
        while (!_st.empty()) {
            int now = _st.back();
            _st.pop_back();
            cmp[now] = k;
            while (true) {
                int nxt = (unvisited & einv[now])._Find_first();
                if (nxt >= V) break;
                _st.push_back(nxt);
                unvisited.reset(nxt);
            }
        }
    }

    // Detect strongly connected components and return # of them.
    // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed)
    DirectedGraphSCC64(const std::vector<std::bitset<VMAX>> &edge,
                       const std::vector<std::bitset<VMAX>> &edge_inv)
        : V(edge.size()), e(edge), einv(edge_inv), cmp(edge.size()), scc_num(0) {
        unvisited.set();
        for (int i = 0; i < V; i++)
            if (unvisited[i]) _dfs(i);
        unvisited.set();
        for (int i = (int)vs.size() - 1; i >= 0; i--)
            if (unvisited[vs[i]]) { _rdfs(vs[i], scc_num++); }
    }
};
#line 3 "graph/test/strongly_connected_components_bitset.test.cpp"
#include <cassert>
#include <stdio.h>

constexpr int VMAX = 10000;
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    assert(V <= VMAX);
    std::vector<std::bitset<VMAX>> e(V), einv(V);
    while (E--) {
        int s, t;
        scanf("%d %d", &s, &t);
        e[s][t] = einv[t][s] = 1;
    }
    DirectedGraphSCC64<VMAX> graph(e, einv);

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d\n", graph.cmp[u] == graph.cmp[v]);
    }
}
Back to top page