백준_1717_집합의 표현
https://www.acmicpc.net/problem/1717
1717번: 집합의 표현
첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a
www.acmicpc.net
해결 방법
> Disjoint set을 이용한다.
> input() 대신에 sys.stdin.readline()을 이용한다.(시간의 차이)
코드
import sys
sys.setrecursionlimit(10**6)
def find(index):
if index != data[index]:
data[index] = find(data[index])
return data[index]
def union(x,y):
data[find(y)] = find(x)
a, b = map(int, sys.stdin.readline().split())
data = list(range(a + 1))
for i in range(b):
x, y, z = map(int, sys.stdin.readline().split())
if x == 0:
union(y - 1,z - 1)
else:
if find(y-1) == find(z-1):
print("YES")
else:
print("NO")