解くに至った問題（2問）
ABC:076C
AtCoder Typical Contest001:B
AtCoder Typical Contest001:B
Union Find木についての問題 これを解く前にABC075Cの連結判定の問題をにらみつけて時間を溶かしていた そういうのの解法はいろいろあるけど、辺の連結を判定するにはUF木がよいとのこと（チーター本のp.370くらいに載ってた これマジでC問題か？）
UF木のUの字も聞いたことのないプログラミングド素人が適当にかみ砕きながらあくまで自分のためだけに説明する
UFとは社会である 子会社のもとをたどれば親会社に、そして部下の上には必ず上司がいるように.......
簡単に言えばどの要素とどの要素が連結しているか（この連結は、何か他の要素を介して辿れるものもふくめて）を便利に扱えるもの
予めゴールを決めておいて、同じ集合の要素であれば、どの要素からも遡っていった先がそのゴールにたどり着くような設計になっている このゴールの事を根（多分「ね」って読むんでしょう）という これが集合の要素を代表している値である
要素がn個あり、m本の辺で連結されているとしよう
まず、par(多分parentの略）とrankという空のリストを用意しておく
それから、
par = [0,1,2,......,n-1] #n個の要素
rank = [0,0,0,......,0] #n個の要素
とする
parは、par[i]を上にたどっていった先の「根」が何かを表すものである
rankは、その「根」である要素jに対し、rank[j]が根の深さを表す。木のように要素が辺で連なっていると考えたとき、末端の要素から根がめっちゃ離れていればrank[j]は大きくなる
UFを扱うための操作として、findとuniteとsameという三つがある
find(x,par)
これは、要素xがparの中で、どれを根としているのかを表している したがって
def find(x,par):
if x == par[x]: #これはx自身が根であることを表している
return x
else:
return find(par[x],par) #par[x]はxの上にあるものを表す par[x]を辿ることで、最
終的にxの根が見つかる
unite(x,y,par,rank)
これは、要素xと要素yが属する集合をくっつける操作である
def unite(x,y,par,rank):
x = find(x,par)
y = find(y,par) #x,yの根を見つける
if x != y: #x,yの根が違えば、
if rank[x] < rank[y]: #根っこの深さを比較し、根っこが深い方に浅い方をくっつける
par[x] = y （この場合、xの根をyに変更する）
else:
par[y] = x
if rank[x] == rank[y]: #根っこの深さが同じ場合は片側のランクを＋１する
rank[x] += 1
same(x,y,par)
これは、x,yの根を比較するための操作である
def same(x,y,par):
return find(x,par) == find(y,par) #Trueなら1、Falseなら0が返ってくる
これらを組み合わせれば、晴れてUF木の扱いができる
例えば、AtCoder Typical ContestのB問題のように一つずつクエリが与えられた際には、①要素と要素をつなげる場合にはuniteを使えばよいし、②要素と要素が連結しているかどうかを判定する場合にはsameを使って判定すればよい
（今回の実装は0インデックスなので、例えば島の番号が1から始まっていたりしたら、入力を-1するといったことに注意する）
だから、ABC075Cの問題は、縦に与えられた入力を「要素を辺でつなげる操作」と解釈し、例えば1番目の辺を除いたすべてをUF木としたとき、連結していれば（つまり、取り除いた1番目の辺が橋でないならば）すべての要素の根が一致するはずであると考えることで、橋の本数は、それをM番目の辺までやったときに、連結していない（根がすべての要素で一致しなかった）UF木の数を数えてやれば求まると分かる また今度やってみます
今回もじゅっぴーダイアリーにお世話になりました ありがとうございました
