AtCoder Beginner Contest 177 D - Friends【Python】
https://atcoder.jp/contests/abc177/tasks/abc177_d
AtCoder ProblemsでDifficulty: 732、Solve Probability: 34%でした。
Union-Findで友達同士であるものをグループとし、すべてのグループのメンバーの最大値が答えになりました。
from collections import defaultdict class UnionFind: def __init__(self,n): self.n=n self.parents=[-1]*n def Find(self,x): stack=[] while self.parents[x]>=0: stack.append(x) x=self.parents[x] for y in stack: self.parents[y]=x return x def Union(self,x,y): x=self.Find(x) y=self.Find(y) if x==y: return if self.parents[x]>self.parents[y]: x,y=y,x self.parents[x]+=self.parents[y] self.parents[y]=x def Size(self,x): return -self.parents[self.Find(x)] def Same(self,x,y): return self.Find(x)==self.Find(y) def Members(self,x): root = self.Find(x) return [i for i in range(self.n) if self.Find(i)==root] def Roots(self): return [i for i, x in enumerate(self.parents) if x<0] def Group_Count(self): return len(self.Roots()) def All_Group_Members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.Find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.All_Group_Members().items()) N, M = map(int, input().split()) UF = UnionFind(N) for _ in range(M): A, B = map(int, input().split()) A -= 1 B -= 1 UF.Union(A, B) ans = 0 for v in UF.All_Group_Members().values(): ans = max(ans, len(v)) print(ans)