[백준] # 4195 친구 네트워크

www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

def find(x):
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    if x!= y:
        parent[y] = x
        number[x] += number[y]

test_case = int(input())   
for _ in range(test_case):
    parent = dict()
    number = dict()
    
    f=int(input())
    for _ in range(f):
        x, y = input().split(' ')
        if x not in parent:
            parent[x]=x
            number[x]=1
        if y not in parent:
            parent[y]=y
            number[y]=1
        union(x, y)
        print(number[find(x)])

* Union-Find 알고리즘을 사용하여 문제를 풀었다

* Path compreesion 기법을 사용하였다

* 새로운 연관 노드를 Union 할때마다 최상위 Parent 노드에 +1 해준다

* 결과적으로 최상위 노드의 number 값이 해가 된다