[백준 4195번] 친구 네트워크 (Python3)

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는 유용하다