풀이

1. 노드가 각각 숫자가 아닌 사람 이름으로 주어진 것에 주의해야한다.
   1.1 숫자 테이블을 선언하여 문자별로 어떤 수에 대응되는지 확인할 수 있다
   1.2 부모 테이블에 바로 이름값을 넣는걸로 부모를 직접 가리킬 수 있다.

1.2 방법을 선택했을 때, union과정에서 어떤 기준으로 하위노드를 설정할지 그 기준을 명확히 세워야한다.

따라서 union 연산을 실행할 때 뒤에 나오는 노드가 무조건 더 하위 노드인 것으로 구현할 수 있다.

• union find에서 노드에 따로 이름이 적혀있으면 대소 비교하기 쉽지않다.
• 위의 예시의 경우 Barney가 1을 부모로 가지는데 1이 Fred를 의미한다는 mapping용 테이블이 하나 더 있어야 한다.
• 그냥 이름을 그대로 value로 사용해도 된다.

def union(friend_cnt,parent,a,b):
    a=find(parent,a)
    b=find(parent,b)
    if a!=b:
        parent[b]=a

2. 항상 parent 배열을 순회하며, 같은 root node를 가지는 사람 수가 몇 명인지 찾을 필요는 없다. union과정에서 자식노드가 가지고 있는 친구의 수를 부모노드에 더해주면 된다.

def find(parent,a):
    if parent[a]!=a:
        parent[a]=find(parent,parent[a])
    return parent[a]

이때 부모노드는 find 함수에서 최상위 root노드를 가리키게 경로 압축을 적용해 최종적으로 같은 네트워크 내에서 root노드에 해당 네트워크의 총 인원수가 들어가게 된다.

아래의 예시를 들어보자

3
Fred Barney
Barney Betty
Betty Wilma

관계가 추가될때마다 union과정에서 root노드에 "네트워크 내 사람 수"를 더해주는 것을 확인할 수 있다.

이는 이전의 union함수에서의 수정이 필요하다. friend_cnt[a]+=friend_cnt[b]를 추가하여 함수를 완성해주자.

def union(friend_cnt,parent,a,b):
    a=find(parent,a)
    b=find(parent,b)
    if a!=b:
        parent[b]=a
        friend_cnt[a]+=friend_cnt[b]

전체 코드는 아래와 같다. 주석을 해제하면 주요한 변수들의 값 변화를 확인할 수 있다.

import sys
input=sys.stdin.readline

def find(parent,a):
    if parent[a]!=a:
        parent[a]=find(parent,parent[a])
    return parent[a]

def union(friend_cnt,parent,a,b):
    a=find(parent,a)
    b=find(parent,b)
    if a!=b:
        parent[b]=a
        friend_cnt[a]+=friend_cnt[b]


for _ in range(int(input())):
    f=int(input())
    parent_map={}
    friend_cnt={}
    for i in range(f):
        a,b=input().split()
        if a not in parent_map.keys():
            parent_map[a]=a
            friend_cnt[a]=1
        if b not in parent_map.keys():
            parent_map[b]=b
            friend_cnt[b]=1
        
        union(friend_cnt,parent_map,a,b)
        
        print(i)
        print(parent_map)
        print(friend_cnt)
        print(friend_cnt[parent_map[a]])
        print("*"*10)