백준 4195 : 문제링크

  • 문제유형 : 해시, 배열, 구현

  • 설명

    • python에서 dictionary 자료형으로 HASH 구현가능

    • Union Find 알고리즘 이용

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    def find(x):
        if parent[x] == x:
            return x
        else:
            p = find(parent[x])
            parent[x] = p
            return parent[x]

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

        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)])