[백준] 4195번 : 친구 네트워크

4195번: 친구 네트워크

해당 문제는 서로소 집합 문제로 해결할 수 있습니다.

왼쪽 친구의 부모로 계속 합치면서 현재 친구상황을 파이썬의 set자료구조에서 union을 통하여 친구네트워크를 업데이트 합니다.

import sys
input = sys.stdin.readline

def find(name):
    if parent[name] == name:
        return parent[name]
    else:
        parent[name] = find(parent[name])
        return parent[name]

def union(name1, name2):
    p1 = find(name1)
    p2 = find(name2)

    if p1 == p2:
        return

    parentset[p1] = parentset[p1].union(parentset[p2])
    parent[p2] = p1

T = int(input())
for _ in range(T):
    N = int(input())
    parent = dict()
    parentset = dict()
    for _ in range(N):
        a, b = map(str, input().split())
        if a not in parent:
            parent[a] = a
            parentset[a] = set()
            parentset[a].add(a)
        if b not in parent:
            parent[b] = b
            parentset[b] = set()
            parentset[b].add(b)

        union(a, b)
        p = find(a)
        print(len(parentset[p]))

<aside> 💡 실제로 친구를 저장하지 않고 개수를 업데이트 함으로서 메모리최적화와 속도를 개선 할 수 있습니다. 만약 친구리스트를 출력해야하는경우는 위의 문제가 알맞을 수 있습니다.

</aside>

import sys
input = sys.stdin.readline

T = int(input())

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
        return parent[a]
    else:
        return parent[a]

def union(a, b):
    parent[b] = a
    friend[a] += friend[b]

for _ in range(T):
    F = int(input())
    friend = dict()
    parent = dict()
    for i in range(F):
        friend1, friend2 = map(str, input().split())
        
        if friend1 not in parent:
            parent[friend1] = friend1
            friend[friend1] = 1
            
        if friend2 not in parent:
            parent[friend2] = friend2
            friend[friend2] = 1
        
        v1 = find(friend1)
        v2 = find(friend2)
        
        if v1 != v2:
            union(v1, v2)
        
        print(friend[find(friend1)])