자료구조 - 서로소 집합

1. 서로소 집합이란?

서로소 집합(Disjoint Set)이란 교집합이 공집합인 집합들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조이다.

- Union 연산 : 어떤 두 원소 a, b에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산

- Find 연산 : 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환

 

2. 서로소 집합의 표현(Disjoint Set, Union-Find)

 

3. 서로소 집합의 구현 및 최적화

1) 초기화 : parent 배열에 i원소에 대한 부모 노드 번호를 저장, 루트 노드인 경우 자기 자신의 번호를 저장

function initialize()
	for i : 1 ~ N
    	parent[i] = i

2) Union 연산 : 하나의 루트 노드를 다른 하나의 루트 노드의 자식 노드로 넣어 두 트리를 합친다.

function union(a, b)
	aRoot = find(a)
    bRoot = find(b)
    parent[aRoot] = bRoot

3) Find 연산 : 주어진 원소의 루트 노드 번호를 반환한다.

function find(a)
	if (parent[a] == a) return a
    else return find(parent[a])
   
function find(a)
	if (parent[a] == a) return a
    else return parent[a] = find(parent[a])