题解

一道很板的并查集，最后统计集合数量就行

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,t;
int read(){
    int x=0,f=1;
    int ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0' and ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }return x*f;
}
void write(int x){
    if(x==0){
        putchar('0');
        return ;
    }if(x<0){
        putchar('-');
        x=-x;
    }if(x>9)write(x/10);
    putchar(x%10+'0');
} 
struct FA{
    int fa[N],h[N];
    int find(int x){
        if(fa[x]==x)return x;
        else return fa[x]=find(fa[x]);
    }void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        if(h[y]<h[x])swap(x,y);
        if(h[x]==h[y])h[y]=h[x]+1;
        fa[y]=x;
    }void init(int n){
        for(int i=1;i<=n;i++)fa[i]=i,h[i]=1;
    }
};
signed main(){
    t=read();
    FA fa;
    while(t--){
        int n=read(),m=read(),ans=0;
        fa.init(n);
        for(int i=1;i<=m;i++){
            int x=read(),y=read();
            fa.merge(x,y);
        }for(int i=1;i<=n;i++){
            if(fa.fa[i]==i)ans++;
        }write(ans);
        putchar('\n');
    }
    return 0;
}

时间复杂度： $O(tmα(n))$ 。其中 $α()$ 为反阿克曼函数。