Disjoint Set Union
(cpstl/ds/Dsu.hpp)

• View this file on GitHub
• Last update: 2025-07-27 21:21:37+09:00
• Include: #include "cpstl/ds/Dsu.hpp"

概要

集合族を管理するデータ構造．集合の併合 (merge) や指定した $2$ 要素が同じ集合に属するかの判定 (same) などが非常に高速に行える．

使い方

コンストラクタ

(1) Dsu()
(2) Dsu(int N)

1. 空の Dsu を作成する．
2. 集合族を $\lbrace \lbrace 1 \rbrace, \lbrace 2 \rbrace, \dots, \lbrace N-1 \rbrace \rbrace$ で初期化する．

計算量

1. $\mathrm{O}(1)$ time
2. $\mathrm{O}(N)$ time

leader

int leader(int x)

x の属する集合の代表元を返す．

計算量

• amortized $\mathrm{O}(\alpha(N))$ time

merge

bool merge(int a, int b)

a, b の属する集合を併合し，元々異なる集合に属していたかを返す．

計算量

• amoritzed $\mathrm{O}(\alpha(N))$ time

same

bool same(int a, int b)

a と b が同じ集合に属するか返す．

計算量

• amortized $\mathrm{O}(\alpha(N))$ time

size

int size(int x)

x が属する集合の大きさを返す．

計算量

• amortized $\mathrm{O}(\alpha(N))$ time

groups

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

集合ごとに配列にまとめた配列を返す．

計算量

• $\mathrm{O}(N\alpha(N))$ time

Verified with

• verify/ds/lc-Union-Find-Dsu.test.cpp

Code

#pragma once

#include <vector>

namespace cpstd {

// Disjoint Set Union
// union by size + path compression

class Dsu {
	private:
	int _n;
	std::vector<int> tree;

	int _leader(int x) {
		return tree[x] < 0 ? x : tree[x] = _leader(tree[x]);
	}

	public:
	Dsu() {}
	explicit Dsu(int n) : _n(n), tree(n, -1) {}

	// `x` の属する集合の代表元を返す
	// amortized O(α(N)) time
	int leader(int x) {
		assert(0 <= x && x < _n);
		return tree[x] ? x : _leader(tree[x]);
	}

	// `a`, `b` の属する集合を併合し，元々異なる集合に属していたかを返す
	// amortized O(α(N)) time
	bool merge(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		a = _leader(a), b = _leader(b);
		if (a == b) return false;
		if (tree[a] > tree[b]) std::swap(a, b);
		tree[a] += tree[b];
		tree[b] = a;
		return true;
	}

	// `a` と `b` が同じ集合に属するか返す
	// amoritized O(α(N)) time
	bool same(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		return _leader(a) == _leader(b);
	}

	// `x` が属する集合の大きさを返す
	// amortized O(α(N)) time
	int size(int x) {
		assert(0 <= x && x < _n);
		return -tree[_leader(x)];
	}

	// 集合ごとに配列にまとめた配列を返す
	// O(Nα(N)) time
	std::vector<std::vector<int>> groups() {
		std::vector<std::vector<int>> mem, res;
		for (int i = 0; i < _n; ++i) mem[_leader(i)].push_back(i);
		for (int i = 0; i < _n; ++i) {
			if (!mem[i].empty()) res.emplace_back(mem[i]);
		}
		return res;
	}
};
};

#line 2 "cpstl/ds/Dsu.hpp"

#include <vector>

namespace cpstd {

// Disjoint Set Union
// union by size + path compression

class Dsu {
	private:
	int _n;
	std::vector<int> tree;

	int _leader(int x) {
		return tree[x] < 0 ? x : tree[x] = _leader(tree[x]);
	}

	public:
	Dsu() {}
	explicit Dsu(int n) : _n(n), tree(n, -1) {}

	// `x` の属する集合の代表元を返す
	// amortized O(α(N)) time
	int leader(int x) {
		assert(0 <= x && x < _n);
		return tree[x] ? x : _leader(tree[x]);
	}

	// `a`, `b` の属する集合を併合し，元々異なる集合に属していたかを返す
	// amortized O(α(N)) time
	bool merge(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		a = _leader(a), b = _leader(b);
		if (a == b) return false;
		if (tree[a] > tree[b]) std::swap(a, b);
		tree[a] += tree[b];
		tree[b] = a;
		return true;
	}

	// `a` と `b` が同じ集合に属するか返す
	// amoritized O(α(N)) time
	bool same(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		return _leader(a) == _leader(b);
	}

	// `x` が属する集合の大きさを返す
	// amortized O(α(N)) time
	int size(int x) {
		assert(0 <= x && x < _n);
		return -tree[_leader(x)];
	}

	// 集合ごとに配列にまとめた配列を返す
	// O(Nα(N)) time
	std::vector<std::vector<int>> groups() {
		std::vector<std::vector<int>> mem, res;
		for (int i = 0; i < _n; ++i) mem[_leader(i)].push_back(i);
		for (int i = 0; i < _n; ++i) {
			if (!mem[i].empty()) res.emplace_back(mem[i]);
		}
		return res;
	}
};
};

Back to top page