Disjoint Set

분리집합이란 교집합이 존재하지 않는 두개 이상의 집합을 관리하는 자료구조이다. 서로소 집합, Union - Find라고도 부른다.

1. Find

주어진 원소(start point)의 부모 node를 반복적으로 탐색하여, 최종적으로 root node를 return한다.

• 테이블의 윗줄이 자식 node, 아래쪽이 부모node이다.
• 6번node의 부모는 5번node다, 5번node의 부모는 4번node다
• 이렇게 작성한 테이블의 node를 따라가면 주어진 노드의 root node를 찾을 수 있다.
• root 노드가 동일하다면 같은 집합인 것이다.

parent = [i for i in range(N + 1)] # 리스트에 저장되는 값이 부모node

def find_parent(sp):               # 부모를 찾아 반복하는 함수라는 의미
    if sp != parent[sp]:           # 자식과 부모가 다르면 
		parent[sp] = find_parent(parent[sp])

	# sp 노드의 부모값을 찾고 그 값의 부모를, 또 그 값의 부모를 찾아가는 과정
    return parent[sp]

• parent : 초기에 인덱스와 값을 동일하게 주었는데 이는 자식node == 부모node라는 의미다.
• 현재 자식node가(sp) == 자식node의 부모node(rep[sp])와 같다면 sp가 root node라는 의미이다.
• find(rep[sp]) : 자식 node의 부모 node를 원소로 한번 더 부모node를 탐색한다.
• return rep[sp] : find함수의 재귀가 끝이 나면 return sp(최종 root node)를 반환 받아 rep[sp]에 담겨지고 이것을 return 받는다.

2. Union

교집합이 존재하지 않는 두 개의 집합을 합치는 연산이다. 각 집합의 root node를 찾아서, A집합의 root node를 B집합의 root node의 부모로 설정하여 두 집합의 root node를 동일하게 해준다. 즉 두 집합은 하나의 집합이 된다.

• {1, 2} , {4, 5, 6} 서로 다른 이 두개의 집합을 합치려한다.
• root node는 각각 1, 4이다.
• 4번 node의 부모 node로 설정한다.
• 두 집합은 1번 node를 root node로 하는 하나의 집합이 된다.

def union(sp,ep):
   rep[find_set(sp)] = find_set(ep)

• sp와 ep 각각의 root node를 찾는다.
• ep를 sp의 부모 노드로 설정해준다.
• sp를 ep의 부모로 둬도 상관없다.

💯 백준 예시문제

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

def union(sp,ep):
    parent[find_parent(sp)] = find_parent(ep)

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

for _ in range(M):
    flag, sp, ep = map(int,input().split())
    if flag :
        if find_parent(sp) == find_parent(ep) :
            print("YES")
        else :
            print("NO")
    else : union(sp, ep)

• Disjoint를 활용한 대표 문제다.
• 하지만, 재귀를 돌면서 recursionError가 발생하기 때문에 sys.setrecursionlimit(107)** 재귀 깊이를 늘려줘야한다.