unionfind
(kyopro/library/datastructure/unionfind.cpp)

• View this file on GitHub
• Last update: 2022-07-20 00:04:43+09:00
• Link: View error logs on GitHub Actions



Verified with

• kyopro/test/set_enumerate.test.cpp
• kyopro/test/unionfind_yosupo-judge.test.cpp

Code

/*
* @title unionfind
* @docs kyopro/docs/unionfind.md
*/

//0-indexed
struct unionfind {
	vector<int> par, siz;

	unionfind(int n) : par(n), siz(n) {
		for (int i = 0; i < n; ++i) {
			//全部根で初期化
			par[i] = i;
			//サイズは1
			siz[i] = 1;
		}
	}

	void init(int n) {
		par.resize(n);
		siz.resize(n);
		for (int i = 0; i < n; ++i) {
			//全部根で初期化
			par[i] = i;
			//サイズは1
			siz[i] = 1;
		}
	}

	//根を返す
	int find(int a) {
		return par[a] == a ? a : par[a] = find(par[a]);
	}

	//くっつける。元から同じだったらfalseを返す
	bool unite(int a, int b) {
		int x = find(a), y = find(b);
		if (x == y)return false;
		else if (siz[x] < siz[y]) {
			par[x] = y;
			siz[y] += siz[x];
		}
		else if (siz[x] > siz[y]) {
			par[y] = x;
			siz[x] += siz[y];
		}
		else {
			par[x] = y;
			siz[y] += siz[x];
		}
		return true;
	}

	//同じ集合か判定する
	bool same(int a, int b) {
		return find(a) == find(b);
	}

	//サイズを返す
	int size(int a) {
		return siz[find(a)];
	}

};

#line 1 "kyopro/library/datastructure/unionfind.cpp"
/*
* @title unionfind
* @docs kyopro/docs/unionfind.md
*/

//0-indexed
struct unionfind {
	vector<int> par, siz;

	unionfind(int n) : par(n), siz(n) {
		for (int i = 0; i < n; ++i) {
			//全部根で初期化
			par[i] = i;
			//サイズは1
			siz[i] = 1;
		}
	}

	void init(int n) {
		par.resize(n);
		siz.resize(n);
		for (int i = 0; i < n; ++i) {
			//全部根で初期化
			par[i] = i;
			//サイズは1
			siz[i] = 1;
		}
	}

	//根を返す
	int find(int a) {
		return par[a] == a ? a : par[a] = find(par[a]);
	}

	//くっつける。元から同じだったらfalseを返す
	bool unite(int a, int b) {
		int x = find(a), y = find(b);
		if (x == y)return false;
		else if (siz[x] < siz[y]) {
			par[x] = y;
			siz[y] += siz[x];
		}
		else if (siz[x] > siz[y]) {
			par[y] = x;
			siz[x] += siz[y];
		}
		else {
			par[x] = y;
			siz[y] += siz[x];
		}
		return true;
	}

	//同じ集合か判定する
	bool same(int a, int b) {
		return find(a) == find(b);
	}

	//サイズを返す
	int size(int a) {
		return siz[find(a)];
	}

};

Back to top page