【ABC177 D】「Friends」を解く【Python3】

N人の人を複数のグループに分け「同じグループの中に友達がいない」という状況を最小のグループ数で作る問題です。

提出

from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

t = [[] for _ in range(n+1)]

for a, b in ab:
    t[a].append(b)
    t[b].append(a)

ans = 1
frag = [True]*(n+1)
d = deque()

for i in range(1, n+1):
    if not frag[i]:
        continue
    d.append(i)
    l = []
    while d:
        num = d.popleft()
        for j in t[num]:
            if not frag[j]:
                continue
            d.append(j)
            l.append(j)
            frag[j] = False
    ans = max(ans, len(set(l)))

print(ans)

同じグループの中には友達がいない、という話なので、友達同士でグループを作り、その中で一番多いグループの人数がそのまま答えになります。

for a, b in ab:
    t[a].append(b)
    t[b].append(a)

上記の部分で、友達同士を配列内のお互いの要素に加えていきます。

入力例1の場合、一つ目のfor文の後のtは、以下のようになっています。

t = [[], [2, 5], [1], [4], [3], [1]]

A₁と友達なのはA₂とA₅ということがわかります。

ここで、A₂とA₅に他に友達がいれば、A₁とも友達だということになります。

二つ目のfor文で、友達の友達を調べています。

for i in range(1, n+1):
    if not frag[i]:
        continue
    d.append(i)
    l = []
    while d:
        num = d.popleft()
        for j in t[num]:
            if not frag[j]:
                continue
            d.append(j)
            l.append(j)
            frag[j] = False
    ans = max(ans, len(set(l)))

人数分の配列fragを作っておき、一度調べた人をFalseにします。

i=1から調べていくとして、最初、配列dには1のみが入っています。

「num = d.popleft()」で左端から1を取り出します。

（今回のように左端から要素を取得するときには、dequeを使用すると、時間短縮になります）

t[1]を調べると、2と5が入っているため、この二つをdに加え、fragをFalseにします。

ここまでの処理で、dには[2, 5]が入っているので、

「num = d.popleft()」で今度は、2を取り出し、t[2]を調べます。

今回は、t[2]、t[5]ともに、1しか入っていないため、この二つを調べて終わりですが、t[2]、t[5]に他の数字が入っていれば、dにそれが加えられるので、その数字の友達も調べることになります。

同時に配列lにも、友達を入れておき、最終的に「len(set(l))」で人数を確かめます。

それが「ans」より大きければ、「ans」に代入します。

最後に「ans」に入っている数字が答えとなるので、これを出力します。