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

문제 링크

 

1717번: 집합의 표현

---

문제

---

문제해결하기

 기본적인 Union-Find 문제로, Union-Find를 이해했다면 쉽게 풀 수있는 문제이다.

개념정리 보러가기 ↓

 

[개념정리] 유니온 파인드(Union-Find) by "union by rank"| (python, 파이썬)

초기에 자신을 가르키는 n+1개의 집합, 즉 n+1개의 노드들을 tree라는 리스트에 담아주었다.

---

정답코드

import sys
input = sys.stdin.readline

class Node :
    def __init__(self,key):
        self.key = key
        self.parent = self
        self.rank = 0

def make_set(x) :
    return Node(x)

def find(x) :
    while x.parent != x :
        x = x.parent
    return x 

def union(x,y) :
    v,w = find(x),find(y)
    if v.rank > w.rank :
        v,w = w,v
    v.parent = w
    if v.rank == w.rank :
        w.rank +=1

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

for i in range(m) :
    a,b,c = map(int, input().split())
    if a :
        if find(tree[b]) == find(tree[c]) : print("YES")
        else : print("NO")
    else :
        union(tree[b],tree[c])