Union-Find 続き

昨日に続いて 10583 Ubiquitous Religions と 10608 Friends を解いた。どちらも Union-Find の簡単な問題。

Ubiquitous Religions は、校内の人数と同じ宗教を持つ二人の組が列挙されたとき、校内には最大でどれだけの宗教があり得るかを出力する問題。幾つ集合があるかを数えるだけです。

Friends は、市民の人数と友達同士である二人の組が列挙されたとき、最も友達が多いグループを探してその人数を出力する問題。こちらは要素数が最大の集合を探してその要素数を出せば完了。

なんとなーく分かってきたかな、というところ。 The Algorithmist には他にも色々なアルゴリズムで解ける問題やアルゴリズムの紹介もあるのでお薦めです。

次は Union-Find を使って最小全域木を求める Kruskal’s algorithm をやろうかと思ってます。