백준 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 |
접근 방식
: union-find 정석 문제.
- root라는 리스트에 각 원소의 루트(부모) 저장하고 시작.
- 합집합 만들기 => root를 같게 하기
- 같은 집합에 포함되어 있는지 확인하기 => root가 같은지 확인
알게된 점
최대 재귀한도 깊이 설정 : sys.setrecursionlimit(200000)
이를 해주지 않으면 런타임 에러가 뜬다.
코드
import sys
sys.setrecursionlimit(200000)
def find(v):
if v == root[v] :
return v
root[v] = find(root[v])
return root[v]
def union(a, b):
a = find(a)
b = find(b)
if a > b : root[a] = b
else: root[b] = a
n, m = map(int, sys.stdin.readline().split())
root = [i for i in range(n+1)]
for _ in range(m):
c, a, b = map(int, sys.stdin.readline().split())
if c == 0: #합집합
union(a, b)
elif c == 1: #같은 집합인지 확인
if find(a) == find(b):
print("YES")
else:
print("NO")
