https://www.acmicpc.net/problem/1717
시간 2초, 메모리 128MB
input :
- n m(1 ≤ n ≤ 1,000,000)(1 ≤ m ≤ 100,000)
- 합집합은 0 a b의 형태로 입력이 주어진다.
- 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다.
output :
- 1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다.
그냥 set을 이용해서도 가능할까 싶지만 개수가 생각보다 많다.
딕셔너리를 이용해서 모든 n에 대해서 집합을 다 만들어 버리면 괜찮지 않을 까 했지만 이보다 쉬운 방법으로
union - find를 사용하는 방법이 존재한다.
동일한 부모 노드를 가리키는 것을 합집합이라고 생각하면 된다.
import sys
sys.setrecursionlimit(100000)
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(a, b):
parent_a = find(a)
parent_b = find(b)
if parent_a > parent_b:
parent[parent_a] = parent_b
else:
parent[parent_b] = parent_a
n, m = map(int, sys.stdin.readline().split())
parent = [i for i in range(n + 1)]
for i in range(m):
c, a, b = map(int, sys.stdin.readline().split())
if c == 0:
if find(a) != find(b):
union(a, b)
else:
print("YES" if find(a) == find(b) else "NO")
