mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Union-Find
(data_structure/union_find.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "data_structure/union_find.hpp"

Union-Find

使い方

$n$ を Union-Find のサイズとする

• union_find(int size) : サイズ $size$ の Union-Find を生成する
• bool unite(int x, int y) : x と y をマージする。マージが成功したときに true を返す $O(\alpha(n))$
• bool is_same(int x, int y) : x と y が同じグループかを返す $O(\alpha(n))$
• int get_size(int x) : x が属する集合のサイズを返す $O(1)$
• int groups_size() : Union-Find の集合の数を返す $O(1)$
• vector<vector<int>> groups() : 集合の状態を表した二次元配列を返す。 $O(N)$

概要

Union-Find です。

Required by

• 二重辺連結成分分解 (graph/two_edge_connected_components.hpp)

Verified with

• verify/aoj/dsl/1_A.test.cpp
• verify/aoj/grl/2_A.test.cpp
• verify/yosupo/two_edge_connected_components.test.cpp
• verify/yosupo/unionfind.test.cpp

Code

#pragma once

#include<cassert>
#include<vector>

struct union_find {
	std::vector<int> v;
	int g_size;
	int n;

	union_find(size_t size) : v(size, -1), g_size(size), n(size) {}

	int root(int x){
		assert(x < n);
		return (v[x] < 0 ? x : v[x] = root(v[x]));
	}

	bool is_root(int x){
		assert(x < n);
		return root(x) == x;
	}

	bool unite(int x, int y){
		assert(x < n && y < n);
		x = root(x);
		y = root(y);
		if(x != y){
			if(v[x] > v[y])std::swap(x, y);
			v[x] += v[y];
			v[y] = x;
			g_size--;
			return true;
		}
		return false;
	}

	bool is_same(int x,int y){
		assert(x < n && y < n);
		return root(x) == root(y);
	}

	int get_size(int x){
		assert(x < n);
		x = root(x);
		return -v[x];
	}

	int groups_size(){
		return g_size;
	}

	std::vector<std::vector<int>> groups(){
		std::vector<std::vector<int>> member(n);
		for(int i = 0;i < n;i++){
			member[root(i)].push_back(i);
		}

		std::vector<std::vector<int>> ret;
		for(int i = 0;i < n;i++){
			if(member[i].empty())continue;
			ret.push_back(member[i]);
		}
		return ret;
	}
};

#line 2 "data_structure/union_find.hpp"

#include<cassert>
#include<vector>

struct union_find {
	std::vector<int> v;
	int g_size;
	int n;

	union_find(size_t size) : v(size, -1), g_size(size), n(size) {}

	int root(int x){
		assert(x < n);
		return (v[x] < 0 ? x : v[x] = root(v[x]));
	}

	bool is_root(int x){
		assert(x < n);
		return root(x) == x;
	}

	bool unite(int x, int y){
		assert(x < n && y < n);
		x = root(x);
		y = root(y);
		if(x != y){
			if(v[x] > v[y])std::swap(x, y);
			v[x] += v[y];
			v[y] = x;
			g_size--;
			return true;
		}
		return false;
	}

	bool is_same(int x,int y){
		assert(x < n && y < n);
		return root(x) == root(y);
	}

	int get_size(int x){
		assert(x < n);
		x = root(x);
		return -v[x];
	}

	int groups_size(){
		return g_size;
	}

	std::vector<std::vector<int>> groups(){
		std::vector<std::vector<int>> member(n);
		for(int i = 0;i < n;i++){
			member[root(i)].push_back(i);
		}

		std::vector<std::vector<int>> ret;
		for(int i = 0;i < n;i++){
			if(member[i].empty())continue;
			ret.push_back(member[i]);
		}
		return ret;
	}
};

Back to top page