ABC279F并查集理解与拓展应用

#include <stdio.h>
const int M=6e5+5, N=9e5+9;
int n, m, i, j, k, x, y, a, b, f[N], s[N];
int find(int x){
    if(f[x] > M) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        f[i] = i+M, s[i+M] = i;
    }//父亲超过M为祖先，s记录box集合的祖先
    while(m--){
        scanf("%d%d", &k, &x);
        if(k == 1){
            scanf("%d", &y);
            a = s[x+M], b = s[y+M];//合并两个集合
            if(!b) continue;
            if(!a) f[b] = x+M, s[x+M] = b;//加入空box
            else f[b] = a;//合并到祖先a
            s[y+M] = 0;//清空box
        }
        else if(k == 2){
            if(s[x+M]) f[++n] = s[x+M];//合并集合
            else f[++n] = x+M, s[x+M] = n;//空box
        }
        else printf("%d\n", f[find(x)]-M);//还原
    }
    return 0;
}