Union Find
(lib/data-structure/union-find.hpp)

• View this file on GitHub
• Last update: 2020-06-22 16:37:39+09:00
• Include: #include "lib/data-structure/union-find.hpp"

Verified with

• test/data-structure/union-find.test.cpp

Code

#pragma once
class UnionFind{
public:
	vector<int>par,rank;
	UnionFind(int n){
		par.resize(n);rank.resize(n,0);
		for(int i=0;i<n;++i)par[i]=i;
	}
	int root(int x){
		return x==par[x]?x:par[x]=root(par[x]);
	}
	bool same(int x,int y){
		return root(x)==root(y);
	}
	void unite(int x,int y){
		x=root(x);
		y=root(y);
		if(x==y)return;
		if(rank[x]<rank[y])par[x]=y;
		else{
			par[y]=x;
			if(rank[x]==rank[y])++rank[x];
		}
	}
};

/**
* @title Union Find
*/

#line 2 "lib/data-structure/union-find.hpp"
class UnionFind{
public:
	vector<int>par,rank;
	UnionFind(int n){
		par.resize(n);rank.resize(n,0);
		for(int i=0;i<n;++i)par[i]=i;
	}
	int root(int x){
		return x==par[x]?x:par[x]=root(par[x]);
	}
	bool same(int x,int y){
		return root(x)==root(y);
	}
	void unite(int x,int y){
		x=root(x);
		y=root(y);
		if(x==y)return;
		if(rank[x]<rank[y])par[x]=y;
		else{
			par[y]=x;
			if(rank[x]==rank[y])++rank[x];
		}
	}
};

/**
* @title Union Find
*/

Back to top page