test/ConnectedComponent.test.cpp

• View this file on GitHub
• Last update: 2021-03-14 18:03:15+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_11_D

Depends on

• Graph/ConnectedComponent.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_11_D"
#include "./../Graph/ConnectedComponent.cpp"
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	auto [k, id, ind] = ConnectedComponent(g);
	int q;
	cin >> q;
	while (q--) {
		int s, t;
		cin >> s >> t;
		cout << (id[s] == id[t] ? "yes" : "no") << '\n';
	}
}

#line 1 "test/ConnectedComponent.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_11_D"
#line 2 "Graph/ConnectedComponent.cpp"
#include <vector>
#include <tuple>

auto ConnectedComponent(const std::vector<std::vector<int>>& graph) {
	int n = graph.size(), count_components = 0;
	std::vector<int> id(n, -1);
	std::vector<std::vector<int>> groups(n);
	auto dfs = [&](auto&& f, int ID, int v) -> void {
		id[v] = ID;
		groups[ID].push_back(v);
		for (int u : graph[v]) {
			if (id[u] == -1) f(f, ID, u);
		}
	};
	for (int i = 0; i < n; ++i) {
		if (id[i] == -1) dfs(dfs, count_components++, i);
	}
	groups.resize(count_components);
	return std::tuple(count_components, id, groups);
}
#line 3 "test/ConnectedComponent.test.cpp"
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	auto [k, id, ind] = ConnectedComponent(g);
	int q;
	cin >> q;
	while (q--) {
		int s, t;
		cin >> s >> t;
		cout << (id[s] == id[t] ? "yes" : "no") << '\n';
	}
}

Back to top page