Union Find(서로소 집합) 개념 및 기본 자바 코드

개념

- 서로소나 상호배타 집합으로, 교집합이 없는 집합.

- 집합의 대표자(식별자) 존재하여 각 집합을 대표함.

- 서로소 집합은 연결 리스트, 트리로 표현 가능함.

 

대표 연산 3가지

(1) make-set(x)

x를 유일하게 포함하는 새로운 집합을 생성한다.

 

(2) find-set(x) 

x를 포함하는 집합을 찾는다.

 

(3) union(x, y)

x,y를 포함하는 두 집합을 찾는다.

 

기본 코드 (Java)

int N; // N개의 원소 존재
int[] parents;	// 원소들마다의 부모

// init
void make(){
    for(int i=0;i<N;i++){
        parents[i] = i;
    }
}

// 대표자 찾기
int findSet(int a){
	if(parents[a] == a) return a;
	// Path Compression
	return parents[a] = findSet(parents[a]); // 내 부모를 대표자로 바꿔버림
}

boolean union(int a, int b){
	// 대표자 찾기
	int aRoot = findSet(a);
	int bRoot = findSet(b);
    
	// 같은 집합이면 합칠 필요 없음.
	if(aRoot == bRoot) return false;
	
	parents[bRoot] = aRoot; // 대표자 바꾸기
	return true;
}