Union-Find木 (graph/union_find.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-02-23 23:13:08+09:00

なにこれ

$n$ 頂点を持つ Union-Find 木．

コンストラクタ

• UnionFind(n)
• UninoFind(n, f1)
• UninoFind(n, f2)
• UnionFind(n, f1, f2)

n 頂点の Union-Find 木を構築する．

• UnionFind(v, f2)
• UnionFind(v, f1, f2)

各頂点が配列 v の要素をデータとして持つ Union-Find 木を構築する．

function<bool(int,int,T&,T&)> f1 はマージテクの swap 判定関数．
function<void(T&,T&)> f2 はデータのマージを行う関数．(左の引数が親の値)
$n \leq 10^8$ 程度．(保持するデータの大きさによる)

メンバ関数

• root(x)：頂点 x が属する木の根を返す．
• size(x)：頂点 x が属する木のサイズを返す．
• merge(x, y)：頂点 x と y を結合し，属する木の根を返す．
• same(x, y)：頂点 x と y が同じ木に属するか判定する．
• tnum()：木の数を返す．

計算量

• コンストラクタ：$O(n)$
• root(x)：ならし $O(\log n)$
• size(x)：ならし $O(1)$
• merge(x, y)：ならし $O(1)$
• same(x, y)：ならし $O(1)$
• tnum()：$O(1)$

Verified with

• test/aoj_DSL_1_A.cpp
• test/yosupo_unionfind.cpp
• test/yuki_0556.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<class T = int> struct UnionFind {
private:
	vector<int> parent;
	vector<int> num;
	vector<T> val;
	int treenum;

	const function<bool(int, int, T &, T &)> swap_flg =
		[this](const int l, const int r, const T &, const T &) { return num[l] < num[r]; };
	const function<void(T &, T &)> merge_val = [this](T &, const T &) {};

public:
	UnionFind(int n) : parent(n), num(n, 1), treenum(n) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, function<bool(int, int, T &, T &)> f1) :
		parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, const function<void(T &, T &)> f2) :
		parent(n), num(n, 1), val(n), treenum(n), merge_val(f2) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
		parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1), merge_val(f2) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(vector<T> &v, const function<void(T &, T &)> f2) :
		parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), merge_val(f2) {
		for(int i = 0; i < v.size(); i++) parent[i] = i;
	}
	UnionFind(vector<T> &v, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
		parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), swap_flg(f1), merge_val(f2) {
		for(int i = 0; i < v.size(); i++) parent[i] = i;
	}

	int root(int x) {
		assert(x < parent.size());
		if(parent[x] == x) return x;
		return parent[x] = root(parent[x]);
	}

	int size(int x) {
		assert(x < parent.size());
		return num[root(x)];
	}

	int merge(int x, int y) {
		assert(x < parent.size() && y < parent.size());
		int xrt = root(x);
		int yrt = root(y);
		if(xrt == yrt) return xrt;
		if(swap_flg(xrt, yrt, val[xrt], val[yrt])) swap(xrt, yrt);
		parent[yrt] = xrt;
		num[xrt] += num[yrt];
		merge_val(val[xrt], val[yrt]);
		treenum--;
		return xrt;
	}

	bool same(int x, int y) {
		assert(x < parent.size() && y < parent.size());
		return root(x) == root(y);
	}

	int tnum() {
		return treenum;
	}

	inline T &operator[](int x) {
		assert(x < parent.size());
		return val[x];
	}
};

#line 2 "graph/union_find.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<class T = int> struct UnionFind {
private:
	vector<int> parent;
	vector<int> num;
	vector<T> val;
	int treenum;

	const function<bool(int, int, T &, T &)> swap_flg =
		[this](const int l, const int r, const T &, const T &) { return num[l] < num[r]; };
	const function<void(T &, T &)> merge_val = [this](T &, const T &) {};

public:
	UnionFind(int n) : parent(n), num(n, 1), treenum(n) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, function<bool(int, int, T &, T &)> f1) :
		parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, const function<void(T &, T &)> f2) :
		parent(n), num(n, 1), val(n), treenum(n), merge_val(f2) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(int n, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
		parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1), merge_val(f2) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	UnionFind(vector<T> &v, const function<void(T &, T &)> f2) :
		parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), merge_val(f2) {
		for(int i = 0; i < v.size(); i++) parent[i] = i;
	}
	UnionFind(vector<T> &v, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
		parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), swap_flg(f1), merge_val(f2) {
		for(int i = 0; i < v.size(); i++) parent[i] = i;
	}

	int root(int x) {
		assert(x < parent.size());
		if(parent[x] == x) return x;
		return parent[x] = root(parent[x]);
	}

	int size(int x) {
		assert(x < parent.size());
		return num[root(x)];
	}

	int merge(int x, int y) {
		assert(x < parent.size() && y < parent.size());
		int xrt = root(x);
		int yrt = root(y);
		if(xrt == yrt) return xrt;
		if(swap_flg(xrt, yrt, val[xrt], val[yrt])) swap(xrt, yrt);
		parent[yrt] = xrt;
		num[xrt] += num[yrt];
		merge_val(val[xrt], val[yrt]);
		treenum--;
		return xrt;
	}

	bool same(int x, int y) {
		assert(x < parent.size() && y < parent.size());
		return root(x) == root(y);
	}

	int tnum() {
		return treenum;
	}

	inline T &operator[](int x) {
		assert(x < parent.size());
		return val[x];
	}
};

Back to top page