서로소 집합

disjoint set 이란 원소를 서로 공유하지 않는 set들의 집합을 말한다.

간단하게 말하자면 [1, 2, 3] 과 [4, 5] 는 서로 겹치는 원소가 없으므로 disjoint set 이다.

하지만 [1, 2, 3] 과 [1, 4] 는 겹치는 원소가 있기 때문에 disjoint set이 아니다.

해당 개념은 보통 그래프를 표현 할 때 많이 사용되게 된다.

일상 생활에서도 disjoint set 으로 나타 낼 수 있는 것들이 많다.

대학생의 성적을 모아놓은 set은 disjoint set이다. A를 받으면서 동시에 B를 받을수는 없기 때문이다.

disjoint set을 컴퓨터과학에서 표현 할 때에는 주로 트리의 형식을 많이 사용한다.

왜냐하면 모든 disjoint set을 하나의 공통 조상을 가지는 트리로 만들어놓으면 빠르게 노드들이 같은 set에 속한지 아닌지를 알 수 있기 때문이다.

disjoint set에서 특정 노드가 어떤 set에 속하는지 알아보는 연산을 FIND 라고 한다.

disjoint set에서 두 개의 노드들을 합치는 연산을 UNION 이라고 한다.

그래서 disjoint set 알고리즘들을 보통 유니온 파인드 알고리즘이라 많이 부르고 실제로도 많이 쓰인다.

가장 자주 쓰이는 것은 무방향 그래프에서 사이클을 찾을 때 자주 쓰인다.

C++ 로 유니온 파인드 알고리즘을 구현 할 때에, 배열을 사용한다. 배열은 항상 모든 원소가 자신의 인덱스의 값으로 초기화된 상태로 시작해야 한다.

이는 모든 원소가 처음 시작할 때에는 자기 자신만을 원소로 가지는 set으로 표현됨을 의미한다.

 int arr[N]
 for(int i = 0; i< N; i++){
   arr[i] = i;
 }

FIND의 C++구현은 다음과 같다. 경로 압축이 포함된 코드이다.

 int Find(int a){
   if(a == parent[a])
       return a;
   return parent[a] = Find(parent[a]);
 }

UNION의 C++구현은 다음과 같다.

 void Union(int a, int b){
   int c = Find(a);
   int d = Find(b);
   if(c != d)
       parent[c] = d;
 }