백준 1717 집합의 표현(python, Union-Find)

* 문제 링크: https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

* 문제 해결방법: Union-Find

1. 입력이 100,000개까지 가능하므로, 완탐으로 풀면 무조건 시간초과

2. 0을 입력받는 족족 Union

3. 1을 입력받는 순간 Find(x) == Find(y): print("YES")

import sys n, m = map(int, sys.stdin.readline().rstrip().split()) arr = [-1] * (n+1) def union(x, y):     a, b = find(x), find(y)     if (a==b):         return     if a>b:         arr[a] = arr[b]         arr[b] = a     else:         arr[b] = arr[a]         arr[a] = b def find(x):     if(arr[x] < 0):         return x     arr[x] = find(arr[x])     return arr[x] for i in range(m):     a,b,c = map(int, sys.stdin.readline().rstrip().split())     if not(a):         union(b, c)     else:         if find(b) == find(c):             print("YES")         else:             print("NO")

 

* 관련 추천문제: 4195 친구 네트워크