Union Find

그룹을 만들고 같은 그룹인지 확인하는 알고리즘

부모 정보를 담은 배열

int Parent[] = new int[N+1];

초기 부모는 자신

for(int i=1; i<=N; i++) {
	Parent[i] = i;
}

Find

가장 상단에 있는 부모를 찾기
찾아가면서 현재 부모도 업데이트

static int find(int a) {
    if(Parent[a] == a) return a;
    
    return Parent[a] = find(Parent[a]);
}

Union

부모를 업데이트할 때는 부모가 둘중 작은/큰 값으로 업데이트
아래 예시에서는 작은 값이 부모가 되게 업데이트하였음

static void union(int a, int b) {
    a = find(a);
    b = find(b);
    
    if (a < b) Parent[b] = a;
    else Parent[a] = b;
}

Tip

그룹을 확인하는 알고리즘은 Union Find도 있지만, DFS로 찾을 수도 있다.

1. 모든 노드를 방문할 때까지 2,3을 반복
2. 한 노드에서 연결되어 더이상 연결할 수 있는 노드가 없을 때
3. 거기까지 그룹