백준 14595 동방탈출 c++ (분리 집합 응용)

분리집합 응용문제를 하나 들고 왔습니다. 분리집합에 관한 기본적인 지식은 생략하고

해당 문제의 핵심 아이디어만 아래 코드블럭의 주석에 구체적이게 달아 놓았으니 참고하세요!

#include<iostream>
using namespace std;
#include<stdio.h>

int n, m,cnt;
int arr[1000000];


int find(int a) {
	if (arr[a] == a)
		return a;
	else
		return arr[a] = find(arr[a]);
}

void join(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return;
	arr[a] = b; //두번째 파라미터가 첫번째 파라미터의 부모가 된다. 
			
}


int main() {
	scanf("%d %d", &n, &m);
	cnt = n;
	for (int i = 1; i <= n; i++) {
		arr[i] = i;
	}
	int x, y;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
        x--,y--;
		while (find(x) != find(y)) {//x~y 범위 모든 원소를 join 연산시 시간초과.
            
            
			--cnt;// 서로 다른 두 그룹을 합칠때마다 그룹의 개수가 1개씩 줄어든다. 
			int nxt = find(x) + 1;
            //root 가 가장 큰 수가 되게 ( 가장 오른쪽) 설정해보자.
            // (1 2 3) (4) (5) 의 경우 3이 root  >> 이후엔 find(x)+1 로 바로 옆 덩어리로 이동 가능!
            //  find(x) 시 3 나옴 >> 3+1 4 >> x~y 범위 안에서 연결되있지 않은 덩어리를 O(1)으로 찾기 가능.
            
			join(x, y); // x<y   인데 join 코드는   두번째 파라미터가 부모가 되게 구현함.
			x = nxt;
		}


		
	}
	printf("%d\n", cnt);
	
}