import sys
input = sys.stdin.readline
def findparent(x):
if parent[x] != x:
parent[x] = findparent(parent[x])
return parent[x]
def union(x,y):
parentx,parenty = findparent(x),findparent(y)
if parentx == parenty:
return
cntlist[parentx] += cntlist[parenty]
parent[parenty] = parentx
T = int(input())
for _ in range(T):
parent = {}
cntlist = {}
N = int(input())
for i in range(N):
x,y = input().split()
if not parent.get(x):
parent[x] = x
cntlist[x] = 1
if not parent.get(y):
parent[y] = x
cntlist[findparent(x)] += 1
union(x,y)
print(cntlist[findparent(x)])
간단한 union-find 응용문제
알고리즘을 요약하면,
1. 이름 x,y가 주어지면 x가 그 전에 입력되지 않았을 경우 x의 부모는 x
2. y가 그 전에 입력되지 않았을 경우, y의 부모는 x이고 x가 속한 집합의 크기에 +1을 한다.
3. y가 그 전에 입력되었을 경우 y가 속한 집합을 x에 union하고 x가 속한 집합의 크기에 y가 속한 집합의 크기만큼 더한다.
4. x가 속한 집합의 크기를 출력한다.
오늘의 교훈) union-find는 유용하다