백준: 1717 집합의 표현

문제

1717번: 집합의 표현

 

문제 풀이

 0부터 N까지 집합을 이룰 때, 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하고 반환하는 문제이다. 이는 `Union-Find`를 이해하고 구현하면 문제를 쉽게 해결할 수 있다. 즉, 해당 자료구조를 그대로 구현하면 문제를 풀 수 있다.

 

코드

from sys import stdin


def find(target):
    if target == parent[target]:
        return target
    return find(parent[target])


def union(root_a, root_b):
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b


if __name__ == '__main__':
    n, m = map(int, stdin.readline().split())
    parent = [i for i in range(n + 1)]

    for _ in range(m):
        op, a, b = map(int, input().split())
        find_a, find_b = find(a), find(b)

        if op:
            print('YES' if find_a == find_b else 'NO')
        else:
            union(find_a, find_b)