[Python]유니온파인드 백준 4195

   문제

   https://www.acmicpc.net/problem/4195

해당 문제의 문자열 비교는 파이썬은 딕셔너리를 사용하여 구현하면 편하다.

파이썬 딕셔너리를 모른다면 아래사이트를 참고하면된다.

https://wikidocs.net/16

딕셔너리에 해당 문자열이 있는지 없는지 확인하고 없다면 추가해주고 있다면 유니온파

인드를 사용해 연결해 준다.

def Find(x):
    if p[x]==x:
        return x
    else:
        y = Find(p[x])
        p[x] = y#시간을 줄이는 요소
        return y
 
 
 
def Union(x,y):
    x=Find(x)
    y=Find(y)
    if x!=y:
        p[y]=x#루트노드 합치기
        cnt[x]=cnt[y]+cnt[x]#루트노드 수합치기
 
 
 
import sys
 
 
T=int(sys.stdin.readline())
for _ in range(T):
    p = {}
    cnt = {}
    F=int(sys.stdin.readline())
    for _ in range(F):
        f1,f2=sys.stdin.readline().split()
        if f1 not in p:#f1이 딕셔너리에 없다면
            p[f1]=f1
            cnt[f1]=1
        if f2 not in p:#f2이 딕셔너리에 없다면
            p[f2]=f2
            cnt[f2]=1
 
        Union(f1,f2)
        print(cnt[Find(f1)])