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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#-----------入力1---------------
n = 5 # 人数
lst = [(1, 2), (3, 4), (5, 1)] # 友達関係
#-----------入力2---------------
# n = 4 # 人数
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] # 友達関係
#-----------入力3---------------
#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) # 1からNを、0からN-1に変換しながら、友達グループを作成

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

print('答え =>', ans)

[実行結果(入力1の場合)]

友達グループ [0, 1, 4]

友達グループ [2, 3]

答え => 3

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

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

[実行結果(入力2の場合)]

友達グループ [0, 1, 2, 3]

答え => 4

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

[実行結果(入力3の場合)]

友達グループ [0, 2, 3]

友達グループ [1, 5]

友達グループ [4, 8]

友達グループ [6]

友達グループ [7]

友達グループ [9]

答え 3

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

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