test/graph/scc/aoj-grl-Strongly-Connected-Components.test.cpp

• View this file on GitHub
• Last update: 2023-12-03 13:41:56+08:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C

Depends on

• library/graph/scc.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"

#include <iostream>

#include "../../../library/graph/scc.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	SCC g(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g.add_edge(u, v);
	}
	g.build();
	int q;
	cin >> q;
	while(q--) {
		int u, v;
		cin >> u >> v;
		cout << (g.id[u] == g.id[v]) << "\n";
	}
	return 0;
}

#line 1 "test/graph/scc/aoj-grl-Strongly-Connected-Components.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C"

#include <iostream>

#line 2 "library/graph/scc.hpp"
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

namespace felix {

struct SCC {
public:
	std::vector<int> id;

	SCC() : n(0) {}
	explicit SCC(int _n) : id(_n), n(_n), g(_n), h(_n) {}

	void add_edge(int u, int v) {
		assert(0 <= u && u < n);
		assert(0 <= v && v < n);
		g[u].push_back(v);
		h[v].push_back(u);
	}

	void build() {
		std::vector<int> top;
		top.reserve(n);
		std::function<void(int)> dfs1 = [&](int u) {
			id[u] = 1;
			for(auto v : g[u]) {
				if(id[v] == 0) {
					dfs1(v);
				}
			}
			top.push_back(u);
		};
		for(int i = 0; i < n; i++) {
			if(id[i] == 0) {
				dfs1(i);
			}
		}
		std::fill(id.begin(), id.end(), -1);
		std::function<void(int, int)> dfs2 = [&](int u, int x) {
			id[u] = x;
			for(auto v : h[u]) {
				if(id[v] == -1) {
					dfs2(v, x);
				}
			}
		};
		for(int i = n - 1, cnt = 0; i >= 0; i--) {
			int u = top[i];
			if(id[u] == -1) {
				dfs2(u, cnt);
				cnt++;
			}
		}
	}

	std::vector<std::vector<int>> compress() {
		int sz = *std::max_element(id.begin(), id.end()) + 1;
		std::vector<std::vector<int>> new_g(sz);
		for(int u = 0; u < n; u++) {
			for(auto v : g[u]) {
				if(id[u] == id[v]) {
					continue;
				}
				new_g[id[u]].push_back(id[v]);
			}
		}
		for(int i = 0; i < sz; ++i) {
			std::sort(new_g[i].begin(), new_g[i].end());
			new_g[i].erase(std::unique(new_g[i].begin(), new_g[i].end()), new_g[i].end());
		}
		return new_g;
	}

private:
	int n;
	std::vector<std::vector<int>> g, h;
};

} // namespace felix
#line 5 "test/graph/scc/aoj-grl-Strongly-Connected-Components.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	SCC g(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g.add_edge(u, v);
	}
	g.build();
	int q;
	cin >> q;
	while(q--) {
		int u, v;
		cin >> u >> v;
		cout << (g.id[u] == g.id[v]) << "\n";
	}
	return 0;
}

Back to top page