test/graph/strongly_connected_components/aoj_grl_3_c.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 18:06:54+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

Depends on

• Strongly Connected Components (src/graph/strongly_connected_components.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

#include "src/graph/strongly_connected_components.hpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	StronglyConnectedComponents scc(v);
	for (int i = 0; i < e; ++i) {
		int s, t;
		cin >> s >> t;
		scc.add_edge(s, t);
	}

	scc.build();

	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << (scc.component_id(u) == scc.component_id(v) ? 1 : 0) << endl;
	}

	return 0;
}

#line 1 "test/graph/strongly_connected_components/aoj_grl_3_c.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_C

#line 1 "src/graph/strongly_connected_components.hpp"



#include <algorithm>
#include <vector>

class StronglyConnectedComponents {
private:
	int n;
	std::vector<std::vector<int>> graph, rev_graph;
	std::vector<int> components;

	void dfs(int v, std::vector<bool> &used, std::vector<int> &order) {
		if (used[v]) return;
		used[v] = true;
		for (auto const &nv : graph[v]) dfs(nv, used, order);
		order.push_back(v);
	}

	void rev_dfs(int v, int id, std::vector<int> &components) {
		if (components[v] != -1) return;
		components[v] = id;
		for (auto const &nv : rev_graph[v]) rev_dfs(nv, id, components);
	}

public:
	StronglyConnectedComponents(int n) : n(n), graph(n), rev_graph(n), components(n) {}

	void add_edge(int from, int to) {
		graph[from].push_back(to);
		rev_graph[to].push_back(from);
	}

	int build() {
		std::vector<bool> used(n);
		std::vector<int> order(n);
		for (int i = 0; i < n; ++i) {
			if (used[i]) continue;
			dfs(i, used, order);
		}
		std::reverse(order.begin(), order.end());

		int cnt = 0;
		components.assign(n, -1);
		for (auto const &v : order) {
			if (components[v] != -1) continue;
			rev_dfs(v, cnt, components);
			++cnt;
		}

		return cnt;
	}

	int component_id(int v) { return components[v]; }
};


#line 4 "test/graph/strongly_connected_components/aoj_grl_3_c.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	StronglyConnectedComponents scc(v);
	for (int i = 0; i < e; ++i) {
		int s, t;
		cin >> s >> t;
		scc.add_edge(s, t);
	}

	scc.build();

	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << (scc.component_id(u) == scc.component_id(v) ? 1 : 0) << endl;
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	100 ms	7 MB
g++	01_small_00.in	AC	13 ms	7 MB
g++	01_small_01.in	AC	13 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	01_small_03.in	AC	13 ms	7 MB
g++	02_medium_00.in	AC	13 ms	7 MB
g++	02_medium_01.in	AC	13 ms	7 MB
g++	03_sparse_00.in	AC	12 ms	7 MB
g++	03_sparse_01.in	AC	13 ms	7 MB
g++	03_sparse_02.in	AC	13 ms	7 MB
g++	03_sparse_03.in	AC	14 ms	7 MB
g++	04_dense_00.in	AC	13 ms	7 MB
g++	04_dense_01.in	AC	13 ms	7 MB
g++	04_dense_02.in	AC	14 ms	7 MB
g++	04_dense_03.in	AC	21 ms	7 MB
g++	05_rand_00.in	AC	21 ms	7 MB
g++	05_rand_01.in	AC	24 ms	7 MB
g++	05_rand_02.in	AC	31 ms	8 MB
g++	06_linear_00.in	AC	103 ms	17 MB
g++	06_linear_01.in	AC	109 ms	17 MB
g++	07_linear_00.in	AC	113 ms	18 MB
g++	07_linear_01.in	AC	114 ms	18 MB
g++	08_grid_00.in	AC	124 ms	10 MB
g++	08_grid_01.in	AC	208 ms	11 MB
clang++	00_sample_00.in	AC	12 ms	9 MB
clang++	01_small_00.in	AC	12 ms	9 MB
clang++	01_small_01.in	AC	11 ms	7 MB
clang++	01_small_02.in	AC	13 ms	11 MB
clang++	01_small_03.in	AC	12 ms	11 MB
clang++	02_medium_00.in	AC	12 ms	11 MB
clang++	02_medium_01.in	AC	12 ms	9 MB
clang++	03_sparse_00.in	AC	12 ms	13 MB
clang++	03_sparse_01.in	AC	12 ms	7 MB
clang++	03_sparse_02.in	AC	12 ms	9 MB
clang++	03_sparse_03.in	AC	14 ms	9 MB
clang++	04_dense_00.in	AC	12 ms	7 MB
clang++	04_dense_01.in	AC	12 ms	11 MB
clang++	04_dense_02.in	AC	14 ms	15 MB
clang++	04_dense_03.in	AC	20 ms	9 MB
clang++	05_rand_00.in	AC	21 ms	11 MB
clang++	05_rand_01.in	AC	21 ms	11 MB
clang++	05_rand_02.in	AC	31 ms	12 MB
clang++	06_linear_00.in	AC	133 ms	20 MB
clang++	06_linear_01.in	AC	137 ms	14 MB
clang++	07_linear_00.in	AC	114 ms	19 MB
clang++	07_linear_01.in	AC	159 ms	19 MB
clang++	08_grid_00.in	AC	141 ms	14 MB
clang++	08_grid_01.in	AC	201 ms	16 MB

Back to top page