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