test/data-structure/dsu/yosupo-Unionfind.test.cpp

• View this file on GitHub
• Last update: 2023-07-30 19:34:47+08:00
• Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

• DSU (並查集) (library/data-structure/dsu.hpp)

Code

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

#include <iostream>

#include "../../../library/data-structure/dsu.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	dsu<true> d(n);
	while(q--) {
		int type, u, v;
		cin >> type >> u >> v;
		if(type == 0) {
			d.merge(u, v);
		} else {
			cout << d.same(u, v) << "\n";
		}
	}
	return 0;
}

#line 1 "test/data-structure/dsu/yosupo-Unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include <iostream>

#line 2 "library/data-structure/dsu.hpp"
#include <vector>
#include <cassert>
#include <algorithm>

namespace felix {

template<bool UNION_BY_SIZE = false>
struct dsu {
public:
	dsu() : dsu(0) {}
	explicit dsu(int _n) : n(_n), sz(n, -1) {}
	
	int leader(int u) {
		assert(0 <= u && u < n);
		return (sz[u] < 0 ? u : (sz[u] = leader(sz[u])));
	}
	
	bool merge(int a, int b) {
		a = leader(a), b = leader(b);
		if(a == b) {
			return false;
		}
		if constexpr(UNION_BY_SIZE) {
			if(-sz[a] < -sz[b]) {
				std::swap(a, b);
			}
		}
		sz[a] += sz[b];
		sz[b] = a;
		return true;
	}
	
	int size(int u) { return -sz[leader(u)]; }
	bool same(int a, int b) { return leader(a) == leader(b); }

	std::vector<std::vector<int>> groups() {
		std::vector<std::vector<int>> result(n);
		for(int i = 0; i < n; i++) {
			result[leader(i)].push_back(i);
		}
		result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) {
			return v.empty();
		}), result.end());
		return result;
	}

private:
	int n;
	std::vector<int> sz;
};

} // namespace felix
#line 5 "test/data-structure/dsu/yosupo-Unionfind.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	dsu<true> d(n);
	while(q--) {
		int type, u, v;
		cin >> type >> u >> v;
		if(type == 0) {
			d.merge(u, v);
		} else {
			cout << d.same(u, v) << "\n";
		}
	}
	return 0;
}

Back to top page