verify/aoj-GRL_3_C-strongly_connected_components.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

Depends on

• Strongly Connected Components（強連結成分分解） (algorithm/Graph/Others/strongly_connected_components.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include <iostream>

#include "../algorithm/Graph/Others/strongly_connected_components.hpp"

int main() {
    int n, m;
    std::cin >> n >> m;

    algorithm::SCC scc(n);
    for(int i = 0; i < m; ++i) {
        int s, t;
        std::cin >> s >> t;

        scc.add_edge(s, t);
    }
    auto &&[_, ids] = scc.decompose();

    int q;
    std::cin >> q;

    while(q--) {
        int u, v;
        std::cin >> u >> v;

        std::cout << (ids[u] == ids[v]) << "\n";
    }
}

#line 1 "verify/aoj-GRL_3_C-strongly_connected_components.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C"

#include <iostream>

#line 1 "algorithm/Graph/Others/strongly_connected_components.hpp"



/**
 * @brief Strongly Connected Components（強連結成分分解）
 * @docs docs/Graph/Others/strongly_connected_components.md
 */

#include <algorithm>
#include <cassert>
#include <stack>
#include <utility>
#include <vector>

namespace algorithm {

// Strongly Connected Components（強連結成分分解）.
class SCC {
    int m_vn;                            // m_vn:=(ノード数).
    std::vector<std::vector<int> > m_g;  // m_g[v][]:=(ノードvの隣接リスト).

public:
    SCC() : SCC(0) {}
    explicit SCC(int vn) : m_vn(vn), m_g(vn) {}

    // ノード数を返す．
    int order() const { return m_vn; }
    // 有向辺を張る．
    void add_edge(int from, int to) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        m_g[from].push_back(to);
    }
    // 有向グラフを強連結成分分解する．return pair of (# of SCCs, SCC id of each nodes). O(|V|+|E|).
    std::pair<int, std::vector<int> > decompose() const {
        int num_sccs = 0;               // num_sccs:=(SCCの数).
        std::vector<int> ids(order());  // ids[v]:=(ノードvが属するSCCのID).
        // ord[v]:=(DFS木におけるノードvの行きがけ順序).
        // low[v]:=(DFS木において，ノードvから葉方向への辺を0回以上，後退辺を高々1回用いて到達できるノードwに対するord[w]の最小値).
        std::vector<int> ord(order(), -1), low(order());
        int now = 0;
        std::stack<int> visited;
        auto dfs = [&](auto self, int u) -> void {
            ord[u] = low[u] = now++;
            visited.push(u);
            for(int to : m_g[u]) {
                if(ord[to] == -1) {
                    self(self, to);
                    low[u] = std::min(low[u], low[to]);
                } else {
                    low[u] = std::min(low[u], ord[to]);
                }
            }
            if(low[u] == ord[u]) {
                while(true) {
                    int v = visited.top();
                    visited.pop();
                    ord[v] = order();  // inf.
                    ids[v] = num_sccs;
                    if(v == u) break;
                }
                num_sccs++;
            }
        };
        for(int v = 0; v < order(); ++v) {
            if(ord[v] == -1) dfs(dfs, v);
        }
        return {num_sccs, ids};
    }
    // 強連結成分ごとに各ノードをグループ分けする．
    std::vector<std::vector<int> > scc() const { return scc(decompose()); }
    std::vector<std::vector<int> > scc(const std::pair<int, std::vector<int> > &p) const { return scc(p.first, p.second); }
    std::vector<std::vector<int> > scc(int num, const std::vector<int> &ids) const {
        assert((int)ids.size() == order());
        std::vector<std::vector<int> > sccs(num);
        for(int v = 0; v < order(); ++v) {
            assert(0 <= ids[v] and ids[v] < num);
            sccs[ids[v]].push_back(v);
        }
        return sccs;
    }
    // 強連結成分から構成されるDAGを取得する．
    std::vector<std::vector<int> > directed_acyclic_graph(const std::pair<int, std::vector<int> > &p) const { return directed_acyclic_graph(p.first, p.second); }
    std::vector<std::vector<int> > directed_acyclic_graph(int num, const std::vector<int> &ids) const {
        assert((int)ids.size() == order());
        std::vector<std::vector<int> > dag(num);
        for(int u = 0; u < order(); ++u) {
            assert(0 <= ids[u] and ids[u] < num);
            for(int v : m_g[u]) {
                assert(0 <= ids[v] and ids[v] < num);
                if(ids[v] == ids[u]) continue;
                dag[ids[u]].push_back(ids[v]);
            }
        }
        for(std::vector<int> &edge : dag) {
            std::sort(edge.begin(), edge.end());
            edge.erase(std::unique(edge.begin(), edge.end()), edge.end());
        }
        return dag;
    }
};

}  // namespace algorithm


#line 6 "verify/aoj-GRL_3_C-strongly_connected_components.test.cpp"

int main() {
    int n, m;
    std::cin >> n >> m;

    algorithm::SCC scc(n);
    for(int i = 0; i < m; ++i) {
        int s, t;
        std::cin >> s >> t;

        scc.add_edge(s, t);
    }
    auto &&[_, ids] = scc.decompose();

    int q;
    std::cin >> q;

    while(q--) {
        int u, v;
        std::cin >> u >> v;

        std::cout << (ids[u] == ids[v]) << "\n";
    }
}

Back to top page