[백준] 14595 동방 프로젝트(Large)

유니온 파인드 & 리스트를 이용해서 풀 수 있는 문제다

벽이 허물어 질 때마다 오른쪽에 있는 방과 합쳐주면 된다

그리고 나의 오른칸을 부모의 오른칸으로 바꿔준다!

그럼 이미 부셔진 벽은 확인하지 않고 부셔지지 않은 벽만 확인 할 수 있다!

소스코드

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 1e6 + 5;
int n, m,R[MAXN], p[MAXN];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}
void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    p[x] = y;
}
 
int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        R[i] = i + 1;
    }
    R[n] = -1;
    int ans = n;
    for (int i = 0; i < m; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        while (find(a) != find(b)) {
            ans--;
            R[a] = R[find(a)];
            merge(a, b);
            a = R[a];
        }
    }
    printf("%d\n", ans);
}