[#알고리즘/Union-Find/[백준]4195번: 친구 네트워크(python)]

Question

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

Solution

union-find 알고리즘 동작 방식을 그대로 사용한다. 다른 점은, 인덱스가 정수가 아닌 문자열이므로 기존처럼 리스트가 아닌 딕셔너리를 사용한다. (값 또한 문자열이다.) count 딕셔너리는 루트 노드의 개수를 세기 위함이다.

Code

import sys

input = sys.stdin.readline

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

def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a != b :
        parent[b] = a
        count[a] += count[b]
    

T = int(input())

for _ in range(T) :
    parent = {}
    count = {}
    
    F = int(input())
    for _ in range(F) :
        a, b = input().split()
        
        if a not in parent :
            parent[a] = a
            count[a] = 1
        if b not in parent :
            parent[b] = b
            count[b] = 1
        
        union_parent(parent, a, b)
        print(count[find_parent(parent, a)])