[Union Find]

1. Union FInd 정의

- 서로소 집합(disjoint Set) & 병합 찾기(MergeFind Set)

- 여러 서로소 집합을 가지고 있는 자료구조(서로소 집합이란, 교집합이 없으면서 모든 원소가 각자의 집합을 가지고 있는 집합)

 

2. 구현

1) 자료구조

-집합 자료구조: Tree, root 노드가 집합의 ID라 생각

-노드 자료구조: 배열, parent[i]는 원소 i의 부모 노드를 저장한다.

 

2) 함수

Union 함수: 주어진 원소들을 집합으로 합침

Find 함수: 특정 원소가 어느 집합에 있는지 찾음

 

3) 초기화

-parent[i] = i; //원소의 부모는 자기자신

 

4) 구현

//x의 root노드와 y의 root노드를 비교한 후, 둘이 같지 않다면 y의 root = x로 지정
void Union(int x,int y) {
	x = Find(x);
	y = Find(y);

	if(x != y)
		parent[i] = x;
}



//x 노드의 root노드 반환
int Find(int x) {
	if(x == parent[x]) return x;

	else {
    	int p = Find(parent[x]); //x의 부모 노드의 root를 찾아서 갱신함
        parent[x] = p;
        return p;
    }

}