ABC120-D Decayed Bridges(Union-Find)

ABC120-D Decayed Bridgesに挑戦した。

正直,なんかグラフだな,木を使いそうだなくらいで全然できなかったので公式editorialを読みました。

https://img.atcoder.jp/abc120/editorial.pdf

すると,一行目に衝撃の事実が書かれていました。

「島を頂点、橋を辺としたグラフを考えます。グラフから辺を削除していくのは難しいことが多い」

なななんと,そうなのか,という感じです。左様でしたか。なので逆からやると。つまり,橋を壊していくのではなく橋を架けていく方針です(出力も得られた結果を逆順で出力する)。で,なんやかやと書いてあることは大体理解したら,でもまだ時間がかかりすぎます,と。Union-Findと呼ばれるデータ構造を用いて効率的にやらないと間に合いませんと書いてあります。いろいろ調べると以下のサイト(特にスライド)が非常に参考になりました。

#根を求める
def root(x):
   if par[x] == x:  #自分が親のときは自分が根ということ
       return x
   else:
       #経路圧縮
       par[x] = root(par[x])#自分が親ではないときは,根を自分の親に設定
       return par[x]

このroot関数は,指定した要素の根を返す。自分が根でない場合はすぐ一つ上の親に根を設定する(これで速くなる)。

#xとyが同じ集合(連結成分)に属するかどうか
def same(x, y):
   return root(x) == root(y)

これはよい。rootが同じであれば,同じ連結成分に属すると判断。

#xとyの属する集合を併合
def unite(x,y):
   xx = root(x)
   yy = root(y)
   #xとyのルートが同じなので操作は必要ない(同じ集合に属する)
   if xx == yy:
       return
   ####ランクあり
   if rank[xx] < rank[yy]:
       par[xx] = yy
   else:
       par[yy] = xx
       if rank[xx] == rank[yy]:
           rank[yy] += 1

指定した要素のrootが異なっている場合に結合する。結合するとは,rootを同じにすること。つまり,xの属するグループとyの属するグループを同じにしたいので,xの属するグループ内のすべての要素の親と,yの属するグループ内のすべての要素の親を一致させる(xまたはyの根にする)という処理を書きたくなる(僕だけ?)。こんな感じに。

for x in gourpX:
 par[x] = root(y)

でも,これはしなくてよい。必要なのは,x(またはy)の属するグループの根の親をyの(またはxの)根として設定してやるだけでよい。同じグループに属する下々の要素に対してはその要素の元々のrootを調べてやればよい(それできちんとyのrootが参照されるし,なんなら,root関数の中で根の付け替えをやっているので大丈夫)。ここまでで書いたことが最初に参照したサイトで読んだことである。ここからABC120-D問題を解く際にはもう一工夫必要である。公式editorialの最後に以下のように記載がある。

size(v)・・・頂点vが属するグループと同じグループに属する頂点数を得る

これを追加で実装しないといけないが,uniteの中身をちょこっといじってyればよい(実は苦労した)。

#xとyの属する集合を併合
def unite(x,y):
   xx = root(x)
   yy = root(y)
   #xとyのルートが同じなので操作は必要ない(同じ集合に属する)
   if xx == yy:
       return
   ####ランクあり
   if rank[xx] < rank[yy]:
       par[xx] = yy
       size[yy] += size[xx] #<-------ここ
   else:
       par[yy] = xx
       size[xx] += size[yy] #<-------ここ
       if rank[xx] == rank[yy]:
           rank[yy] += 1

ここでsize[x]はxの属するグループの頂点数を保持する配列である。ここでも同一グループ内のすべての要素iに対しsize[i]を更新したくなるが不要である。ノードの頂点数を更新しておいて,sizeを参照するときはノードを指定してやれば良いからである。これで準備が整った。以下,ソース全文である。

#ノードの数,橋の数
N,M = map(int, input().split())

#最初は自分自身が親(根)
par = [i for i in range(N+1)]
#ランク(深さ)
rank = [0]*(N+1)
#各要素が属するグループのサイズ(連結成分の個数)
size = [1]*(N+1)

#木の根を求める
def root(x):
   if par[x] == x:  #自分が親のときは自分が根ということ
       return x
   else:
       #経路圧縮
       par[x] = root(par[x])#自分が親ではないときは,根を自分の親に設定
       return par[x]

#xとyが同じ集合(連結成分)に属するかどうか
def same(x, y):
   return root(x) == root(y)

#xとyの属する集合を併合
def unite(x,y):
   xx = root(x)
   yy = root(y)
   #xとyのルートが同じなので操作は必要ない(同じ集合に属する)
   if xx == yy:
       return
   ####ランクあり
   if rank[xx] < rank[yy]:
       par[xx] = yy
       size[yy] += size[xx]
   else:
       par[yy] = xx
       size[xx] += size[yy]
       if rank[xx] == rank[yy]:
           rank[yy] += 1

#出力する不便度
ans = [0]*M
#すべての橋が壊れているときの不満度はN個の島から2個の島の選び方の総数と等しい
ans[M-1] = N*(N-1)//2

#橋の情報
B = [list(map(int,input().split())) for i in range(M)]

#橋の情報を逆順に取り出す
for i in range(M-1,0,-1):
   a = B[i][0]
   b = B[i][1]
   if root(a) != root(b):
       ans[i-1] = ans[i] -size[root(a)]*size[root(b)]
   else:
       ans[i-1] = ans[i]
   #橋をつなげる
   unite(a,b)

for a in ans:
   print(a)

これでOK,と思ったら2ケースだけREとなった。RE?と思って(本当は良くないが)テストケースを見てエラーを確認すると

RecursionError: maximum recursion depth exceeded in comparison

と言われた。どうもよく知らないのだが,Pythonには再起処理回数に制限あるらしく,それを超えて再起しようとした際に起こるエラーのようであった。確かにREとなったテストケースは入力数がやたら多かった。このようなときはソースの最初に次を追記すればOK。

import sys
sys.setrecursionlimit(100000)

最後の数値のところが,最大の再起処理回数である(デフォルトは1000らしい)。よくわからいので適当に0を増やして実行したら通りました。

余談ですが,このUnion-Findにおけるfindの操作(ここではroot)の計算量はアッカーマン関数の逆関数が出てくるようです。とても意外でした。そこはまだ勉強できていないのでまたそのうちに勉強したいなぁと思っています。








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