다음과 같은 상황일때 나와 주황색 친구가 서로 연결 되어 있는지 확인하려면 DFS나 BFS를 이용하면 된다.
하지만, 사람이 계속 추가되거나 연결 될때 다시 DFS나 BFS를 이용해서 탐색을 해야 한다. 이는 분리 집합을 이용해 간단하게 구할 수 있다.

다음과 같이 분리를 할 수 있고 나와 주황색과의 관계는 서로 분리 되어 있는 것을 확인해 볼 수 있다.

하지만 다음과 같이 간선이 추가 된다면 나와 주황색이 서로 연결되어 있다는 것을 한번에 알 수 있다.

Union-Find 알고리즘

Union-Find 알고리즘은 분리 집합을 구현하는 알고리즘으로 각 그룹을 다음과 같이 트리로 나타낸다.

각 노드마다 부모 노드 번호를 기록한다.
만약 1과 8번 노드 사이의 관계를 알고 싶으면 부모 노드를 계속 찾아가며 1은 결국 3번 노드가 최상위 노드가 되고, 8은 결국 6번 노드가 최상위 노드가 되므로 친구관계가 아니다.
다음은 이에 대한 구현이다. 구현하는 함수는 다음과 같이 한다.

• root 노드를 찾는 함수
• 두 트리 병합하는 함수

int find_root(int x){
	if (x==parent[x])
		return x; //x가 최상위 노드이면, 그대로 반환
    return find_root(parent[x]); //x가 자식 노드일 때, 부모 노드로 재귀 실행
}

void union_root(int x, int y){
	x = find_root(x);
    y = find_root(y);
    //x, y의 최상위 노드 찾기
    if(x != y){
    	parent[x] = y; //최상위 노드가 서로 다르면 한쪽 트리를 다른 한쪽 트리에 붙힘
    }
}

최적화1

다음과 같이 1000 노드에 1001 노드가 추가로 붙어지면 항상 최상위 노드를 찾으러 1번까지 올라가야 한다. 이를 방지하기 위해 추가 될때마다 그 노드의 부모 노드를 항상 최상위 노드로 만든다.

int find_root(int x){
	if (x == parent[x])
    	return x;
    return parent[x] = find_root(parent[x]);

최적화2

void union_root(int x, int y) {
    //x, y 정점의 최상위 정점을 각각 찾는다. (속한 트리의 루트 노드를 찾는다.)
    x = find_root(x);
    y = find_root(y);
 
    if (x != y) {
        //서로 다른 트리에 속한다면, 한 쪽의 트리를 다른 쪽에 붙인다.
        //***항상 높이가 낮은 트리를 높이가 높은 트리에 붙인다.***
        if (node_rank[x] < node_rank[y]) parent[x] = y;
        else parent[y] = x;
 
        //만약 합친 두 트리의 높이가 같다면, 합친 후 트리의 높이를 1 증가시킨다.
        if (node_rank[x] == node_rank[y]) {
            parent[x] = y;
            node_rank[x]++;
        }
    }
}