[BOJ] 1717. 집합의 표현

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

문제: 0이면 해당 수가 들어가 있는 집합 둘을 합치고 1이면 둘이 같은 집합인지 확인해라.

 

문제 이해하기!!

이 문제는 그냥 유니온 파인드라고 광고를 하고 만든 문제인 것 같습니다.

0일 때, 두 집합을 합치고, 1일 때, find() 함수로 둘의 부모를 확인하면 됩니다.

문제를 풀 때, 한 번 틀렸는데... 최대재귀깊이를 생각 못 해서 ㅠㅠ

근데 요즘 백준에서 왜 틀렸는지를 보여줘서 틀린 것 찾기가 좀 쉬워졌죠^^

바로 recursion error 라고 떠서 바로 고쳐서 통과했습니다!

 

코드 : 

from sys import stdin
input = stdin.readline
import sys
sys.setrecursionlimit(200000)

def find(x):
    if x == arr[x]:
        return x
    else:
        arr[x] = find(arr[x])
        return arr[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        arr[y] = x
    else:
        arr[x] = y

N, M = map(int, input().split())
arr = [i for i in range(N+1)]
for i in range(M):
    a, b, c = map(int, input().split())
    if a == 0:
        union(b, c)
    else:
        if find(b) == find(c):
            print('YES')
        else:
            print('NO')