test/datastructure/disjoint_set_union/aoj_dsl_1_a.test.cpp

• View this file on GitHub
• Last update: 2024-10-03 00:41:55+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A

Depends on

• Disjoint Set Union (Union-Find) (src/datastructure/disjoint_set_union.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A

#include "src/datastructure/disjoint_set_union.hpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	DisjointSetUnion dsu(n);
	while (q--) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 0) dsu.unite(a, b);
		else if (t == 1) {
			if (dsu.same(a, b)) cout << 1 << endl;
			else cout << 0 << endl;
		}
	}

	return 0;
}

#line 1 "test/datastructure/disjoint_set_union/aoj_dsl_1_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A

#line 1 "src/datastructure/disjoint_set_union.hpp"



#include <numeric>
#include <utility>
#include <vector>

class DisjointSetUnion {
private:
	std::vector<int> rank, size, p;
	int num{};

public:
	DisjointSetUnion(int n) : rank(n), size(n, 1), p(n), num(n) {
		std::iota(p.begin(), p.end(), 0);
	}

	bool same(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return;
		--num;
		if (rank[x] < rank[y]) std::swap(x, y);
		if (rank[x] == rank[y]) ++rank[x];
		p[y] = x;
		size[x] += size[y];
	}

	int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

	int get_size(int x) { return size[root(x)]; }

	[[nodiscard]] int forest_size() const { return num; }
};


#line 4 "test/datastructure/disjoint_set_union/aoj_dsl_1_a.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	DisjointSetUnion dsu(n);
	while (q--) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 0) dsu.unite(a, b);
		else if (t == 1) {
			if (dsu.same(a, b)) cout << 1 << endl;
			else cout << 0 << endl;
		}
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	67 ms	7 MB
g++	00_small_01.in	AC	12 ms	7 MB
g++	01_rand_00.in	AC	12 ms	7 MB
g++	01_rand_01.in	AC	12 ms	7 MB
g++	01_rand_02.in	AC	12 ms	7 MB
g++	01_rand_03.in	AC	12 ms	7 MB
g++	01_rand_04.in	AC	14 ms	7 MB
g++	01_rand_05.in	AC	13 ms	7 MB
g++	02_linear_00.in	AC	12 ms	7 MB
g++	02_linear_01.in	AC	16 ms	7 MB
g++	02_linear_02.in	AC	35 ms	7 MB
g++	02_linear_03.in	AC	55 ms	7 MB
g++	03_grid_00.in	AC	13 ms	7 MB
g++	03_grid_01.in	AC	13 ms	7 MB
g++	03_grid_02.in	AC	13 ms	7 MB
g++	03_grid_03.in	AC	13 ms	7 MB
g++	03_grid_04.in	AC	13 ms	7 MB
g++	03_grid_05.in	AC	12 ms	7 MB
g++	03_grid_06.in	AC	13 ms	7 MB
g++	03_grid_07.in	AC	14 ms	7 MB
g++	03_grid_08.in	AC	15 ms	7 MB
g++	04_critical_00.in	AC	35 ms	7 MB
g++	04_critical_01.in	AC	35 ms	7 MB
g++	05_groups_00.in	AC	50 ms	7 MB
g++	05_groups_01.in	AC	63 ms	7 MB
g++	05_groups_02.in	AC	47 ms	7 MB
g++	05_groups_03.in	AC	61 ms	7 MB
g++	05_groups_04.in	AC	63 ms	7 MB
g++	06_randmax_00.in	AC	15 ms	7 MB
g++	06_randmax_01.in	AC	120 ms	7 MB
g++	06_randmax_02.in	AC	116 ms	7 MB
g++	06_randmax_03.in	AC	149 ms	7 MB
clang++	00_small_00.in	AC	11 ms	9 MB
clang++	00_small_01.in	AC	11 ms	15 MB
clang++	01_rand_00.in	AC	11 ms	11 MB
clang++	01_rand_01.in	AC	11 ms	13 MB
clang++	01_rand_02.in	AC	11 ms	13 MB
clang++	01_rand_03.in	AC	11 ms	9 MB
clang++	01_rand_04.in	AC	12 ms	15 MB
clang++	01_rand_05.in	AC	11 ms	9 MB
clang++	02_linear_00.in	AC	11 ms	15 MB
clang++	02_linear_01.in	AC	15 ms	7 MB
clang++	02_linear_02.in	AC	34 ms	13 MB
clang++	02_linear_03.in	AC	36 ms	11 MB
clang++	03_grid_00.in	AC	12 ms	9 MB
clang++	03_grid_01.in	AC	11 ms	13 MB
clang++	03_grid_02.in	AC	11 ms	13 MB
clang++	03_grid_03.in	AC	12 ms	13 MB
clang++	03_grid_04.in	AC	11 ms	11 MB
clang++	03_grid_05.in	AC	12 ms	11 MB
clang++	03_grid_06.in	AC	12 ms	15 MB
clang++	03_grid_07.in	AC	13 ms	13 MB
clang++	03_grid_08.in	AC	12 ms	9 MB
clang++	04_critical_00.in	AC	35 ms	11 MB
clang++	04_critical_01.in	AC	49 ms	13 MB
clang++	05_groups_00.in	AC	54 ms	9 MB
clang++	05_groups_01.in	AC	50 ms	11 MB
clang++	05_groups_02.in	AC	50 ms	7 MB
clang++	05_groups_03.in	AC	64 ms	13 MB
clang++	05_groups_04.in	AC	48 ms	7 MB
clang++	06_randmax_00.in	AC	16 ms	15 MB
clang++	06_randmax_01.in	AC	79 ms	15 MB
clang++	06_randmax_02.in	AC	97 ms	7 MB
clang++	06_randmax_03.in	AC	123 ms	7 MB

Back to top page