test/scc.test.cpp

• View this file on GitHub
• Last update: 2025-06-14 01:07:36+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C

Depends on

• グラフライブラリ (C++/graph/Graph.hpp)
• Strongly Connected Components(強連結成分分解) (C++/graph/SCC.hpp)
• Edge (C++/graph/edge.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"
#include <iostream>
#include "C++/graph/Graph.hpp"
#include "C++/graph/SCC.hpp"
int main() {
    int v, e, q;
    std::cin >> v >> e;
    man::graph<false> g(v, 0);
    g.input(e);
    man::SCC scc(g);
    std::cin >> q;
    while(q--) {
        int a, b;
        std::cin >> a >> b;
        std::cout << int(scc[a] == scc[b]) << '\n';
    }
}

#line 1 "test/scc.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C"
#include <iostream>
#line 2 "C++/graph/Graph.hpp"

#line 4 "C++/graph/Graph.hpp"
#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

#include <ranges>

#ifndef TEMPLATE
namespace man {
template <class T, class U> constexpr inline bool chmin(T& a, const U& b) noexcept { if(a > b){ a = b; return true; } return false; }
}
#endif
#line 2 "C++/graph/edge.hpp"
#ifndef EDGE
#define EDGE
#endif

namespace man {
struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    constexpr inline operator int() const noexcept { return to; }
};
}

/**
 * @brief Edge
 */
#line 15 "C++/graph/Graph.hpp"
namespace man {
template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
    int indexed, id;
    std::vector<edge> edges;
public:
    graph(){}
    graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this->resize(n); }
    inline void add(int a, int b) noexcept {
        a -= indexed, b-= indexed;
        (*this)[a].emplace_back(a, b, id);
        edges.emplace_back(a, b, id++);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id);
            edges.emplace_back(b, a, id++);
        }
    }
    inline void input(const int m) noexcept {
        for([[maybe_unused]] const auto _: std::views::iota(0, m)) {
            int a, b;
            std::cin >> a >> b;
            add(a, b);
        }
    }
    inline std::vector<edge> get_edge() const noexcept { return edges; }
    inline std::vector<int> all_dist(const int v) noexcept {
        std::vector<int> d(this -> size(), -1);
        std::queue<int> q;
        d[v] = 0;
        q.emplace(v);
        while(!q.empty()) {
            const int tmp = q.front();
            q.pop();
            for(const auto &el: (*this)[tmp]) {
                if(d[el] != -1) {
                    continue;
                }
                d[el] = d[tmp] + 1;
                q.emplace(el);
            }
        }
        return d;
    }
    inline int dist(const int u, const int v) noexcept { return all_dist(u)[v]; }
    inline std::vector<int> t_sort() noexcept {
        const int n = this->size();
		std::vector<int> deg(n);
		for(const auto i: std::views::iota(0, n)) {
			for(const auto ed: (*this)[i]) {
				deg[ed]++;
			}
		}
		std::stack<int> sk;
		for(const auto i: std::views::iota(0, n)) {
			if(deg[i] == 0) {
				sk.emplace(i);
			}
		}
		std::vector<int> ord;
		while(!sk.empty()) {
			const auto tmp = sk.top();
            sk.pop();
			ord.emplace_back(tmp);
			for(const auto ed: (*this)[tmp]) {
				if(--deg[ed] == 0) {
					sk.emplace(ed);
				}
			}
		}
		return ord.size() == size() ? ord : std::vector<int>{};
	}
    inline std::vector<edge> cycle() noexcept {
        const int n = size();
        std::vector<int> used(n);
        std::vector<edge> pre(n), cycle;
        const auto dfs = [&](const auto &f, const int i) -> bool {
            used[i] = 1;
			for(const auto &e: (*this)[i]) {
				if(used[e] == 0) {
					pre[e] = e;
					if(f(f, e)) {
						return true;
					}
				} else if(used[e] == 1) {
					int now = i;
					while(now != e) {
						cycle.emplace_back(pre[now]);
						now = pre[now].src;
					}
					cycle.emplace_back(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
        };
        for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs(dfs, i)) {
				std::ranges::reverse(cycle);
				return cycle;
			}
		}
		return {};
    }
};
}

/**
 * @brief グラフライブラリ
 */
#line 2 "C++/graph/SCC.hpp"

#line 6 "C++/graph/SCC.hpp"
namespace man {
template <class G> struct SCC {
private:
	std::vector<int> comp, order, used;
	std::vector<std::vector<int>> group;
	G g, rg, dag;
	inline void dfs(const int i) noexcept {
		if(used[i]) {
			return;
		}
		used[i] = true;
		for(const auto &e: g[i]) {
			dfs(e);
		}
		order.push_back(i);
  	}
  	constexpr inline void rdfs(const int i, const int cnt) noexcept {
    	if(comp[i] != -1) {
			return;
		}
    	comp[i] = cnt;
    	for(const auto &e: rg[i]) {
			rdfs(e, cnt);
		}
  	}
	inline void build() noexcept {
		const int n = std::ssize(g);
		rg = G(n, 0);
		for(const auto i: std::views::iota(0, n)) {
			for(const auto &e: g[i]) {
				rg.add(e.to, e.src);
			}
		}
		used.assign(n, 0);
		comp.assign(n, -1);
		for(const auto i: std::views::iota(0, n)) {
			dfs(i);
		}
		std::ranges::reverse(order);
		int ptr = 0;
		for(const auto &i: order) {
			if(comp[i] == -1) {
				rdfs(i, ptr++);
			}
		}
		dag = G(ptr, 0);
		for(const auto i: std::views::iota(0, n)) {
			for(const auto &e: g[i]) {
				const int x = comp[e.src], y = comp[e.to];
				if(x == y) {
					continue;
				}
				dag.add(x, y);
			}
		}
		group.resize(ptr);
		for(const auto i: std::views::iota(0, n)) {
			group[comp[i]].emplace_back(i);
		}
	}
public:
    SCC(const G &g): g(g){ build(); }
	constexpr inline int operator[](const int i) const noexcept { return comp[i]; }
	inline std::vector<std::vector<int>> groups() const noexcept { return group; }
	inline G DAG() const noexcept { return dag; }
};
}

/**
 * @brief Strongly Connected Components(強連結成分分解)
 * @see https://ei1333.github.io/library/graph/connected-components/strongly-connected-components.hpp
 */
#line 5 "test/scc.test.cpp"
int main() {
    int v, e, q;
    std::cin >> v >> e;
    man::graph<false> g(v, 0);
    g.input(e);
    man::SCC scc(g);
    std::cin >> q;
    while(q--) {
        int a, b;
        std::cin >> a >> b;
        std::cout << int(scc[a] == scc[b]) << '\n';
    }
}

Back to top page