test/disjointSetUnion-test2.test.cpp

View this file on GitHub
Last update: 2023-04-03 07:50:25+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

disjointSetUnion (互いに素な集合の森） (src/dataStructure/disjointSetUnion.hpp)

Code

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

#include "../src/dataStructure/disjointSetUnion.hpp"

#include <cstdio>

int main() {
    int N, Q;
	std::scanf("%d%d", &N, &Q);
    zawa::disjointSetUnion uf(N);
    for (int _ = 0 ; _ < Q ; _++) {
		int t, u, v;
		std::scanf("%d%d%d", &t, &u, &v);
        if (t == 0) uf.merge(u, v);
		else std::printf("%d\n", uf.same(u, v));
    }
}

#line 1 "test/disjointSetUnion-test2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#line 2 "src/dataStructure/disjointSetUnion.hpp"

#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cassert>

namespace zawa {

class disjointSetUnion {
private:
	std::vector<int> parents;
	std::vector<int> sizes;

public:
	disjointSetUnion(std::size_t n) : parents(n, 0), sizes(n, 1) {
		std::iota(parents.begin(), parents.end(), 0);
	}

	int leader(int x) {
		assert(0 <= x and x < (int)parents.size());
		return (parents[x] == x ? x : parents[x] = leader(parents[x]));
	}

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

	void merge(int x, int y) {
		int lx = leader(x), ly = leader(y);
		if (lx == ly) return;
		if (sizes[lx] < sizes[ly]) std::swap(lx, ly);
		sizes[lx] += sizes[ly]; 
		parents[ly] = lx;
	}

	int size(int x) {
		return sizes[leader(x)];
	}

	std::vector<std::vector<int>> groups() {
		std::vector res(parents.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)parents.size() ; i++) {
			res[leader(i)].push_back(i);
		}
		res.erase(std::remove_if(res.begin(), res.end(), 
					[](std::vector<int> x) { return x.empty(); }), res.end());
		return res;
	}
};

}// namespace zawa
#line 4 "test/disjointSetUnion-test2.test.cpp"

#include <cstdio>

int main() {
    int N, Q;
	std::scanf("%d%d", &N, &Q);
    zawa::disjointSetUnion uf(N);
    for (int _ = 0 ; _ < Q ; _++) {
		int t, u, v;
		std::scanf("%d%d%d", &t, &u, &v);
        if (t == 0) uf.merge(u, v);
		else std::printf("%d\n", uf.same(u, v));
    }
}