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

문제 설명

• 친구와 친구 간에 서로 연결된 네트워크가 있을 때, 총 몇 명이 연결 되어 있는가?
• 합집합을 찾는 문제 (Union-Find Algorithm)
• 재귀 함수를 이용하여, 연결된 네트워크를 찾고 또 찾는다.

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)
    # x, y의 부모 값이 다른 경우, y의 부모 값을 x의 부모 값으로 바꾼다.
    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)])

 

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python