disjointSetUnion (互いに素な集合の森）
(src/dataStructure/disjointSetUnion.hpp)

• View this file on GitHub
• Last update: 2023-04-03 07:50:25+09:00
• Include: #include "src/dataStructure/disjointSetUnion.hpp"

概要

zawa::disjointSetUnion(std::size_t n)

Union-Findアルゴリズムを使用し、互いに素な集合の属 ${S_1,\ S_2,\ \dots ,\ S_k}$ に対し以下のクエリを処理することができるデータ構造

• $x$ を含む集合と $y$ を含む集合を合併して和集合を生成する
• $x$ と $y$ が同じ集合に含まれているかを確認する

集合に含まれる元を一つ、代表元とすることでそれぞれの集合を識別する。互いに素(どの集合の組も和集合が空集合)なので、代表元のとり方は重要ではない。

機能

コンストラクタ

zawa::disjointSetUnion(std::size_t n)

$S_0 = \{ 0 \}, S_1 = \{ 1 \}, \dots, S_{n - 1} = \{ n - 1 \}$ と集合族を生成、初期化する

メンバ

leader

int leader(int x)

元 $x$ が含まれる集合の代表元を返す

merge

void merge(int x, int y)

元 $x$ を含む集合と元 $y$ を含む集合を合併する

same

bool same(int x, int y)

元 $x$ と $y$ が同じ集合族に含まれているかを判定する

size

int size(int x)

元 $x$ を含む集合の要素数を返す

groups

std::vector<std::vector<int>> groups()

現在の集合属を返す。元に対して昇順とは限らない

計算量

TODO: 書く

参考

AC Library

• メンバの名前等はこちらに揃えています

アルゴリズムイントロダクション 第二巻

• ドキュメントの文言はこちらを参考にしました

Verified with

• test/disjointSetUnion-test1.test.cpp
• test/disjointSetUnion-test2.test.cpp
• test/disjointSetUnion-unitTest.test.cpp

Code

#pragma once

#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cassert>

namespace zawa {

class disjointSetUnion {
private:
	std::vector<int> parents;
	std::vector<int> sizes;

public:
	disjointSetUnion(std::size_t n) : parents(n, 0), sizes(n, 1) {
		std::iota(parents.begin(), parents.end(), 0);
	}

	int leader(int x) {
		assert(0 <= x and x < (int)parents.size());
		return (parents[x] == x ? x : parents[x] = leader(parents[x]));
	}

	bool same(int x, int y) {
		return leader(x) == leader(y);
	}

	void merge(int x, int y) {
		int lx = leader(x), ly = leader(y);
		if (lx == ly) return;
		if (sizes[lx] < sizes[ly]) std::swap(lx, ly);
		sizes[lx] += sizes[ly]; 
		parents[ly] = lx;
	}

	int size(int x) {
		return sizes[leader(x)];
	}

	std::vector<std::vector<int>> groups() {
		std::vector res(parents.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)parents.size() ; i++) {
			res[leader(i)].push_back(i);
		}
		res.erase(std::remove_if(res.begin(), res.end(), 
					[](std::vector<int> x) { return x.empty(); }), res.end());
		return res;
	}
};

}// namespace zawa

#line 2 "src/dataStructure/disjointSetUnion.hpp"

#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cassert>

namespace zawa {

class disjointSetUnion {
private:
	std::vector<int> parents;
	std::vector<int> sizes;

public:
	disjointSetUnion(std::size_t n) : parents(n, 0), sizes(n, 1) {
		std::iota(parents.begin(), parents.end(), 0);
	}

	int leader(int x) {
		assert(0 <= x and x < (int)parents.size());
		return (parents[x] == x ? x : parents[x] = leader(parents[x]));
	}

	bool same(int x, int y) {
		return leader(x) == leader(y);
	}

	void merge(int x, int y) {
		int lx = leader(x), ly = leader(y);
		if (lx == ly) return;
		if (sizes[lx] < sizes[ly]) std::swap(lx, ly);
		sizes[lx] += sizes[ly]; 
		parents[ly] = lx;
	}

	int size(int x) {
		return sizes[leader(x)];
	}

	std::vector<std::vector<int>> groups() {
		std::vector res(parents.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)parents.size() ; i++) {
			res[leader(i)].push_back(i);
		}
		res.erase(std::remove_if(res.begin(), res.end(), 
					[](std::vector<int> x) { return x.empty(); }), res.end());
		return res;
	}
};

}// namespace zawa

Back to top page