2020/4/11_网易笔试题_操作集合(并查集删点)

哎 实在是太菜了 之后我会补上新解法的

• 并查集基础题，增加一维belong数组表示该点属于哪个集合即可

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 1e3 + 10;

int N,M,S;
int fa[maxn],num[maxn],belong[maxn];
void init(){
    for(int i = 1 ; i <= N; i ++){
        belong[i] = fa[i] = i;
        num[i] = 1;
    } 
}
int finds(int x){return fa[x] != x ? fa[x] = finds(x) : x;}

void Union(int a,int b){
    a = finds(a), b = finds(b);
    if(a == b) return;
    num[a] += num[b];
    fa[b] = a;
}

int main(){
    int T; 
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M); init();
        int cnt = N;
        for(int i = 1; i <= M ; i ++){
            int op; scanf("%d",&op);
            if(op == 1){
                int x,y; scanf("%d%d",&x,&y);
                Union(belong[x],belong[y]);    
            }else if(op == 2){
                int x; scanf("%d",&x);
                num[finds(belong[x])]--;
                belong[x] = ++cnt;
                fa[cnt] = cnt; num[cnt] = 1;
            }else{
                int x; scanf("%d",&x);
                printf("%d\n",num[finds(belong[x])]);
            }
        }
    }
    return 0;
}