[BOJ] 9938 방청소

문제 설명 및 풀이 : http://www.secmem.org/blog/2022/01/16/How_to_approach_problems_7/

주의할 점 : 부모 배열을 p[x] = -1 로 초기화하는 것보다 p[x] = x 로 초기화하면 메모리 초과가 발생하지 않는다.

#include <iostream>

using namespace std;
int N,L;
bool A[300010]; // 0 empty, 1 full
int p[300010];

int find(int x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}
bool Union(int u, int v){
    u = find(u); v = find(v);
    if(A[u] && A[v]) return false;
    else if(!A[u] && !A[v]) {
        p[v] = u;
        A[v] = 1;
    }
    else{
        if(A[u]) swap(u,v);
        A[u] = 1;
        p[v] = u;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N>>L;
    for(int i = 1; i <= L; i++) p[i] = i;
    for(int i = 0; i < N; i++){
        int x,y;cin>>x>>y;
        if(Union(x,y)) cout<<"LADICA\n";
        else cout<<"SMECE\n";
    }
    return 0;
}