問題概要
問題ページ
-
-
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()