Test/UnionFind.test.cpp

• View this file on GitHub
• Last update: 2021-03-09 18:26:45+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• 素集合データ構造 (Union-Find) (DataStructure/UnionFind.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include "DataStructure/UnionFind.hpp"

#include <cstdio>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	UnionFind uf(N);
	while (Q--) {
		int t, u, v;
		scanf("%d %d %d", &t, &u, &v);
		if (t == 0) uf.unite(u, v);
		else printf("%d\n", uf.issame(u, v));
	}
}

#line 1 "Test/UnionFind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#line 1 "DataStructure/UnionFind.hpp"



#include <vector>
#include <utility>
#include <cassert>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/UnionFind.hpp
 */
struct UnionFind {
	using size_type = std::size_t;
	
private:
	size_type n;
	std::vector<int> dat;
	
public:
	explicit UnionFind(size_type n) : n(n), dat(n, -1) {}
	
	size_type size(size_type x) noexcept {
		assert(x < n);
		return -dat[find(x)];
	}
	
	size_type find(size_type x) noexcept {
		assert(x < n);
		if (dat[x] < 0) return x;
		return dat[x] = find(dat[x]);
	}
	
	void unite(size_type x, size_type y) noexcept {
		assert(x < n);
		assert(y < n);
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (dat[x] < dat[y]) std::swap(x, y);
		dat[y] += dat[x];
		dat[x] = y;
	}
	
	bool issame(size_type x, size_type y) noexcept {
		assert(x < n);
		assert(y < n);
		return find(x) == find(y);
	}
};


#line 4 "Test/UnionFind.test.cpp"

#include <cstdio>

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	UnionFind uf(N);
	while (Q--) {
		int t, u, v;
		scanf("%d %d %d", &t, &u, &v);
		if (t == 0) uf.unite(u, v);
		else printf("%d\n", uf.issame(u, v));
	}
}

Back to top page