[백준] 4195번 - 친구 네트워크 (파이썬)

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

# 친구 네트워크

import sys
input = sys.stdin.readline
T = int(input())


def find_parent(x):
    global result
    if x != parent[x]:
        parent[x] = find_parent(parent[x])
    return parent[x]


def union(a, b):
    global result
    x = find_parent(arr[a])
    y = find_parent(arr[b])
    if x < y:
        parent[y] = x
        num[x] += num[y]
    elif x > y:
        parent[x] = y
        num[y] += num[x]


for _ in range(T):
    N = int(input())
    arr = dict()
    n = 0
    parent = [i for i in range(2*N)]
    num = [1] * (2*N)
    for i in range(N):
        a, b = input().split()
        if a not in arr:
            arr[a] = n
            n += 1
        if b not in arr:
            arr[b] = n
            n += 1
        union(a, b)
        print(num[find_parent(arr[a])])

 

Union-Find

1. 입력값을 받을 때, 문자열은 dict의 값에 0부터 하나씩 초기화 해서 받는다

2. union : a와 b의 딕셔너리 값(노드번호)의 부모를 찾아서 더 작은 값의 부모로 초기화, 더 작은 값에 num 더해주기

    find_parent: 해당 노드의 루트부모값 return

3. 둘 중 한명의 루트노드의 num값을 출력

 

기존 union-find에서 문자열 처리와 num값으로 친구숫자 관리가 추가되었다.