[백준] 4195번 친구 네트워크 (Python)

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

4195번: 친구 네트워크

 

 

백준 1717번 '집합의 표현'을 풀었다면 약간의 코드 수정으로 풀 수 있다.

유니온 파인드 문제들은 대부분 결이 비슷한 것 같다.

 

정답 코드

import sys
input = sys.stdin.readline
     
def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        parent[rootA] = rootB
        number[rootB] += number[rootA]
    else:
        return

n = int(input())
for _ in range(n):
    parent = dict()
    number = dict()
    net = int(input())
    for i in range(net):
        name1, name2 = map(str, input().split())

        if name1 not in parent:
            parent[name1] = name1
            number[name1] = 1

        if name2 not in parent:
            parent[name2] = name2
            number[name2] = 1
        
        union(name1, name2)
        print(number[find(name1)])