[Python] 백준 1717번/집합의 표현/유니온파인드 Union Find

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

⚡️ 문제 설명

전형적인 Union Find 문제!

union find 개념을 안다면 바로 풀 수 있는 문제다.

2023.06.16 - [algorithm/개념] - [Python] Union - Find 유니온 파인드/서로소 집합

[Python] Union - Find 유니온 파인드/서로소 집합

⚡️ 해결 방법

union 함수로 자신이 속한 집합을 찾고,

find_parent 함수를 통해 자신의 루트 노드를 찾는다.

루트 노드가 같다면 둘이 같은 집합에 속하기 때문에 YES를 프린트한다.

⚡️ 코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [ i for i in range(n+1) ]

def find_parent(parent, x):
    if parent[x] != x :
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union(parent,x,y):
    x = find_parent(parent, x)
    y = find_parent(parent, y)
    if x<y:
        parent[y] = x
    else:
        parent[x] = y

for _ in range(m):
    check, a, b = map(int, input().split())
    if check == 0:
        union(parent,a,b)
    elif check == 1:
        if find_parent(parent,a) == find_parent(parent,b):
            print("YES")
        else:
            print("NO")