Coding - Algo/python
[백준] 1717번:집합의 표현 (python 파이썬)
jainn
2021. 3. 31. 13:49
728x90
문제
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
유니온 파인드 문제이다.
유니온 파인드에 대해 이해가 가지 않는다면 ,
유니온 파인드(UNION-FIND) 파이썬 구현
유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고
jainn.tistory.com
이 글을 보고 오면 된다!
풀이 및 소스코드
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
n, m = map(int, input().split())
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
parent[x] = y
return
def find(x):
if parent[x] == x:
return x
parent[x]=find(parent[x])
return parent[x]
parent = [0]*(n+1)
for i in range(n+1):
parent[i] = i
for i in range(m):
x, a, b = map(int, input().split())
if x == 0:
union(a,b)
else:
pa = find(a)
pb = find(b)
if pa == pb:
print('YES')
else:
print('NO')반응형