[Algorithm] 유니온 파인드(Union-Find)

✨서로소 집합(Disjoin-set)

공통 원소가 없는 두개 이상의 집합

 

 

 

✨유니온 파인드(Union-Find)

서로소 집합에 대해 union,find 연산을 수행하는 알고리즘
Union:두 개의 집합을 하나의 집합으로 병합
Find:원소가 어떤 집합에 속해있는지를 판단

 

 

 

 

 

 

 

EX) 백준 1717 집합의 표현

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

 

 

 

import sys
sys.setrecursionlimit(1000000)
def getparent(n):
    if(dic[n]==n):return n
    else: 
        dic[n]=getparent(dic[n])
        return dic[n]

def unionparent(a,b):
    n1=getparent(a)
    n2=getparent(b)
    if(n1>n2):dic[n1]=n2
    else:dic[n2]=n1
    
def findparent(a,b):
    if(getparent(a)==getparent(b)):print("YES")
    else:print("NO")



N,M=map(int,sys.stdin.readline().rstrip().split(" "))
dic={}
for i in range(N+1):dic[i]=i

for i in range(M):
    li=list(map(int,sys.stdin.readline().rstrip().split(" ")))
    if(li[0]==0):unionparent(li[1],li[2])
    else:findparent(li[1],li[2])

 

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9