Edit

【pythonでABC177を解説】D - Friends

問題概要

問題ページ

問題文

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

「人 \(A_i\) と人 \(B_i\) は友達である」という情報が \(M\) 個与えられます。同じ情報が複数回与えられることもあります。

\(X\) と \(Y\) が友達、かつ、\(Y\) と \(Z\) が友達ならば、\(X\) と \(Z\) も友達です。また、\(M\) 個の情報から導くことができない友達関係は存在しません。

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

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

制約

  • \(2 \leq N \leq 2\times 10^5\)
  • \(0 \leq M \leq 2\times 10^5\)
  • \(1\leq A_i,B_i\leq N\)
  • \(A_i \neq B_i\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    tmd = collections.defaultdict(list)
    for i in range(m):
        tma, tmb = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]

    fq = collections.defaultdict(list)
    ans = 0
    for i in range(n):
        ql = [[0, i]]
        ql = collections.deque(ql)
        grp = []
        if i not in fq:
            fq[i]
            while True:
                if len(ql) != 0:
                    cost, tmp = ql.popleft()
                    for tmv in tmd[tmp]:
                        if tmv not in fq:
                            ql.append([cost + 1, tmv])
                            fq[tmv]
                            grp.append(tmv)
                else:
                    break
        ans = max(ans, len(grp) + 1)
    print(ans)


if __name__ == '__main__':
    solve()

-Edit
-