[BOJ][🟡4][백준#01717] 집합의 표현

문제 출처

BAEKJOON Online Judge #1717

문제

초기에 {0}, {1}, {2}, … {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

예제

입력

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

출력

NO
NO
YES

My Sol

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def find_set(x):
    if x!=p[x]:
        p[x] = find_set(p[x])

    return p[x]

n, m = map(int, input().split())
p = [i for i in range(n+1)]
for _ in range(m):
    f, u, v = map(int, input().split())
    a, b = find_set(u), find_set(v)

    if f:
        print('YES' if a == b else 'NO')
        continue

    if a != b:
        p[a] = b

유니온 파인드를 이용하여 해결하는 문제였다. 템플릿을 사용하고 일부 변형하는데 어렵지 않게 풀 수 있었다.

결과

맞았습니다!!

모범답안

출처

# empty