Union Find Tree

説明

集合を高速に扱う木構造。

---

情報

項目	データ
計算量	クエリ $O(\alpha)$

関数

UnionFind(size)
機能	初期化
引数	$size$: 大きさ

void unite(x, y)
機能	集合$x$と$y$を併合
引数	$x, y$: 併合する集合

int find(x)
機能	集合$x$の親を求める
引数	$x$: 親を求める集合
戻り値	$x$の親

実装例

問題例

#	ソース	難易度
AOJ DSL_1_A - 互いに素な集合	-
ARC032_B - 道路工事	ARC032 B	★
AOJ 1016 - Fibonacci Sets	UAPC2003	★★
AOJ 2664 - 買い物	RUPC2015	★★★
ARC036_D - 偶数メートル	ARC036 D	★★★
AOJ0575 - JOI国のお祭り事情	JOI2011本選	★★★★