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

접근

유니온파인드 알고리즘을 이용하여 풀 수 있다.

유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python)

백준 1717번: 집합의 표현 (Python)

여기서는 weighted union find를 사용하지 않고 대신 문자형을 받을 수 있는 dictionary를 두개 사용하여 문제를 해결하였다. 기존 리스트들의 역할을 하는 딕셔너리와 집합의 크기를 나타내는 딕셔너리를 각각 이용했다.

코드

import sys


def find(x):
    if connect[x] == x:
        return x
    p = find(connect[x])
    connect[x] = p
    return p


def union(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        connect[y] = x
        number[x] += number[y]
    print(number[x])


for _ in range(int(sys.stdin.readline())):
    connect = dict()
    number = dict()
    for __ in range(int(sys.stdin.readline())):
        a, b = sys.stdin.readline().split()
        if a not in connect:
            connect[a] = a
            number[a] = 1
        if b not in connect:
            connect[b] = b
            number[b] = 1
        union(a, b)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!