Union Find木を使って問題を解く

Union Find木を使って問題を解く

前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

人 1 から 人 N までのN 人の人がいます。

「人Ai と人 Bi は友達である」という情報が M 個与えられます。

同じ情報が複数回与えられることもあります。

X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。

また、M 個の情報から導くことができない友達関係は存在しません。

いじわるな高橋君は、このN人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか？

[条件]

・人数Nは、2以上 200000以下です。

・友達関係の数Mは、0以上 200000以下です。

・AiとBiは、1以上 N以下です。

・AiとBiは、異なる数字です。

[解き方]
Union Find木 を使って友達同士のグループを作ります。

同じグループの中に友達がいない 状況を作るためには、友達の数が一番多いグループの人数分グループ数に分ければよいことになります。

[Google Colaboratory]

n = 5
lst = [(1, 2), (3, 4), (5, 1)]
#-----------入力２---------------
# n = 4
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
#-----------入力３---------------
#n = 10
#lst = [(3, 1), (4, 1), (5, 9), (2, 6)]
#--------------------------------
uf = UnionFind(n)   # 前回記事で実装した「Union Find木」を使う

for l in lst:       # 友達関係から友達グループを作成する
    uf.union(l[0]-1, l[1]-1)

ans = 0             # 友達がいない状況をつくるためのグループ数
for g in uf.all_group_members().values():   # 友達グループごとにループ
    print(f'友達グループ', g)               # 友達グループのメンバー
    g_size = len(g)         # 友達の数
    # 友達の数が「友達がいない状況をつくるためのグループ数」より大きかったら
    if g_size > ans:
        ans = g_size        # グループ数に友達数を設定

print('答え =>', ans)

[実行結果（入力１の場合）]

友達グループ [0, 1, 4]
友達グループ [2, 3]
答え => 3

１つ目の友達グループが３人ともっとも人数が多いので、３グループに分ければよいことになります。

例えば｛0, 2｝｛1, 3｝｛4｝と分ければ、だれも友達がいないグループとなります。

[実行結果（入力２の場合）]

友達グループ [0, 1, 2, 3]
答え => 4

４人全員が友達なので、４グループに分けて全員をばらばらにする必要があります。

[実行結果（入力３の場合）]

友達グループ [0, 2, 3]
友達グループ [1, 5]
友達グループ [4, 8]
友達グループ [6]
友達グループ [7]
友達グループ [9]
答え 3

１つめの友達グループが３人ともっとも人数が多いので、３グループに分けます。

友達が２人の場合は、３グループのうちいずれかの２グループに振り分ければよいですし、友達がいない人は、３グループのどこに分けても友達関係はできません。