機能
- 部分木同士の結合
- 二つのノードが同じグループ(木)かの判定
- あるノードが含まれる部分木のサイズを調べる
namespace template_algorithm {
class union_find {
public:
/// @brief コンストラクタ
union_find(int n) {
roots.assign(n, Pi());
for (int i = 0; i < (int)roots.size(); i++) {
roots[i] = {i, 1};
}
}
/// @brief aとbがそれぞれ含まれる、部分木同士を結合する
void unite(int a, int b) {
a = get_root(a);
b = get_root(b);
//すでに同じ木に含まれる場合
if (a == b) return;
//aの部分木のほうが大きかった場合
if (roots[a].second > roots[b].second) {
roots[b].first = a;
roots[a].second += roots[b].second;
}
//bの部分木のほうが大きかった場合
else {
roots[a].first = b;
roots[b].second += roots[a].second;
}
}
/// @brief ノードa, bが同じ部分木に含まれるかの判定
bool is_same_root(int a, int b) {
a = get_root(a);
b = get_root(b);
return a == b;
}
/// @brief xの根ノードを返す
int get_root(int x) {
if (roots[x].first == x) return x;
roots[x].first = get_root(roots[x].first);
roots[x].second = roots[roots[x].first].second;
return roots[x].first;
}
/// @brief xが含まれる部分木のサイズを返す
int get_tree_size(int x) {
x = get_root(x);
return roots[x].second;
}
private:
using Pi = pair<int, int>;
//first:根ノード second:部分木のサイズ
vector<Pi> roots;
};
}
参考になったサイト
こちらはPythonで書かれていました。(私はPythonは読めないですが…
AtCoderのUnionFindを使う問題などが解説つきで、いくつかまとめられていてわかりやすかったです。↓
【UnionFind】クラスの実装とAtCoder典型問題まとめ【Python】
本記事では,競技プログラミング等で汎用的に扱うことのできるUnionFindクラスの実装を紹介します.そして,AtCoderの問題の解法と共に,その使い方を解説しています.
いくつか紹介されていた問題をC++でACしたので、提出を置いておきます↓
Submission #52821565 - AtCoder Beginner Contest 177
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
Submission #52823474 - AtCoder Regular Contest 106
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
最後に
とりあえず、必要最小限のみの実装となっています。
(まだいくつかほしい機能があるので、また追記する予定です)
AtCoderの問題でもUnionFindは結構でてくるので、よければ使ってくださいね!
もし、「このコード使ったよ」(←励みになります)や「正しく動かないよ」ということがありましたら筆者のX(旧Twitter)まで連絡いただけると助かります。
最後までお読みいただきありがとうございましたっ
( ゚д゚)つ Bye
コメント