UnionFind
(data-structure/UnionFind.hpp)

• View this file on GitHub
• Last update: 2020-09-23 00:24:59+09:00
• Include: #include "data-structure/UnionFind.hpp"

概要

素集合どうしの併合，連結判定などを $O(\alpha(N))$ で行う．
併合はunion by size，経路圧縮にはpath halvingを用いている．

Verified with

• test/yosupo/unionfind.test.cpp

Code

// @brief UnionFind
// @shortcut UnionFind
// @description 素集合データ構造． union by size+path halvingの実装．O(α(N)).
// @docs data-structure/UnionFind.md
class UnionFind {
private:
	std::vector<int> par;
	std::vector<int> siz;

public:
	UnionFind(int sz_) : par(sz_), siz(sz_, 1) {
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(int sz_) {
		par.resize(sz_);
		siz.resize(sz_, 1);
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	int find(int x) {
		while (par[x] != x) x = par[x] = par[par[x]];
		return x;
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (siz[x] < siz[y]) std::swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return siz[find(x)];
	}
};

#line 1 "data-structure/UnionFind.hpp"
// @brief UnionFind
// @shortcut UnionFind
// @description 素集合データ構造． union by size+path halvingの実装．O(α(N)).
// @docs data-structure/UnionFind.md
class UnionFind {
private:
	std::vector<int> par;
	std::vector<int> siz;

public:
	UnionFind(int sz_) : par(sz_), siz(sz_, 1) {
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(int sz_) {
		par.resize(sz_);
		siz.resize(sz_, 1);
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	int find(int x) {
		while (par[x] != x) x = par[x] = par[par[x]];
		return x;
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (siz[x] < siz[y]) std::swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return siz[find(x)];
	}
};

Back to top page