Union-Find Forest 備忘録 p.34

itsuki

2020年12月15日 19:56

itsukiです。
Union-Find Forest ( disjoint-set data structure ) の問題をよく見かけるにもかかわらずその手法を全く知らなかったため、ゼロから履修した様子です。解説記事ではありません。

まずは AtCoder Typical Contest 001 B- Union Find を AC するため、以下の記事（順不同）を参考にしながら My Union-Find Forest を実装しました。大変お世話になりました。

参考記事

「好きなパーツを組み合わせて君だけの UnionFindTree を作ろう！」という記述がとても好きです。

実装

初期実装からすでに改良を加えた状態ですが、現在の My Union-Find Forest の様子です。

#include <stdio.h>
#include <stdbool.h>
typedef long long ll;
void ll_swap(ll*a, ll*b){ ll tmp=(*a); (*a)=(*b); (*b)=tmp;}

//--- 初期化
//--- n:要素数, *par:各元の親の番号, *size:素集合のサイズ
void uf_init(ll n, ll *par, ll *size){
   for(ll i=0; i<n; i++){ par[i]=i; size[i]=1; }
}

//--- x が属する木の根を求める
//--- x:要素, *par:各元の親の番号
ll uf_root(ll x, ll *par){
   if(par[x]==x){ return x;                             }   // 根
   else         { return par[x] = uf_root(par[x], par); }   // 経路圧縮
}

//--- x と y が同じ集合に属するか否か
//--- x:要素1, y:要素2, *par:各元の親の番号
bool uf_same(ll x, ll y, ll *par){
   return uf_root(x,par)==uf_root(y,par);
}

//--- x と y の属する集合を併合
//--- x:要素1, y:要素2, *par:各元の親の番号, *size:素集合のサイズ
bool uf_unite(ll x, ll y, ll *par, ll *size){
   x = uf_root(x,par);
   y = uf_root(y,par);
   if(x==y){ return false; }
   if(size[x] < size[y]){ ll_swap(&x,&y); }
   size[x] += size[y];
   par[y]=x;
   return true;
}

//--- x が属する集合の要素の数
//--- x:要素, *par:各元の親の番号, *size:素集合のサイズ
ll uf_size(ll x, ll *par, ll *size){
   return size[uf_root(x,par)];
}

演習 1. ATC 001 B - Union Find

演習 2. ACLBC C - Connect Cities

ACL ( AtCoder Library ) は未整備だったため ACLBC はリアルタイム参加せず、その後バチャで同じ問題が出たときも解けず、悔しい思いをしていたので AC できて嬉しかったです。

演習 3. ABC 177 D - Friends

リアルタイム参加した際、全く歯が立たなかった問題のひとつです。Twitter で Union-Find だったと聞いていたのでリベンジ。

演習 4. ARC 065 / ABC 049 D - 連結

ここからは、こちらの記事の「Union-find Forest / Disjoint-set data structure」項から適当に選んで演習。お世話になりました。

自分にはあまりにも難しくて丸二日ほど考えました。競プロで構造体を書いたのは久々で、クイックソートの compare 関数を書くのもかなり苦労しました。人生初の青色 AC。

演習 5. ABC 157 D - Friend Suggestions

包除原理（多分）を思いつくまでが長かったです。Twitter で「ABC で "友達" が出てきたらほぼ Union-Find」と聞いたのを思い出しました。

演習 6. ABC 120 D - Decayed Bridges

「Union-Find Forest は辺を削除するのに向いていない」と聞いていたので、しばらく考え込みました。クエリを逆順に処理する方法を思いついてからは早く解けたと思います。切り離すしかなかったら、つなぐ処理に言い換える！（自戒）

演習 7. ABC 075 C - Bridge

与えられるグラフは連結なので、任意の頂点 a_i と頂点 b_i をつながず他の頂点をすべてつないだとき、グラフのサイズが N でないなら、頂点 a_i と頂点 b_i の辺は橋だったと言えます。

演習 8. ARC 106 B - Values

リアルタイム参加した際、全く歯が立たなかった問題のひとつです。どちらの操作を行っても、操作前／操作後でグラフ内の合計値は変わりません。各グラフについて、a_i の合計と b_i の合計が等しいかを確認します。

演習 9. ARC 032 B - 道路工事

問題を読んですぐに実装が思いつき、5分ほどで解けました。ようやく慣れてきたということでしょうか…

まとめ

・Union-Find Forest の基礎は履修できた（はず）なので、演習は一旦終了
・どの問題も Union-Find Forest を使うとはいえ、それぞれ解法が異なるのを見ると本番で出たら厳しそう
・今まで全く歯が立たなかった問題が解けるようになるのは至高

引き続き、のんびり精進します。

#備忘録 #AtCoder #ABC #ARC #ATC #ACLBC #プログラミング #競プロ #C言語 #データ構造

この記事が気に入ったらサポートをしてみませんか？