[백준] 1717번:집합의 표현 (python 파이썬)

문제

www.acmicpc.net/problem/1717

1717번: 집합의 표현

유니온 파인드 문제이다.

유니온 파인드에 대해 이해가 가지 않는다면 ,

jainn.tistory.com/87

유니온 파인드(UNION-FIND) 파이썬 구현

이 글을 보고 오면 된다!

 

 

풀이 및 소스코드

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')