并查集： 并查集适用于不相交的集合问题 题目链接
#include <bits/stdc++.h> using namespace std; int a[10000]; int find_set(int x) { if(x!=a[x]) find_set(a[x]); else return x; } void union_set(int x,int y)//合并并查集 { x=find_set(a[x]); y=find_set(a[y]); if(x!=y) a[x]=a[y]; } int main() { int t;int n,m; cin>>t; while(t--) { cin>>n>>m; for(int i=1;i<=n;i++) { a[i]=i; } for(int i=0;i<m;i++) { int x,y; cin>>x>>y; union_set(x,y); } int ans=0; for(int i=1;i<=n;i++) { if(a[i]==i) ans++; } cout<<ans<<endl; } }在这里的效率不高，合并操作可以优化；在合并元素xy时先搜到他们的根节点，然后合并这两个根节点，即把一个根节点的集改成另一个根节点，这两个的根节点的高度不同，如果把高度较小的集合合并到高度更高的集合上，能减少树的高度；
int heigh[10000]; void init_set() { for(int i=0;i<10000;i++) { a[i]=i; heigh[i]=0;//刚开始的树的高度是0 } } void union_set(int x,int y)//合并并查集 { x=find_set(x); y=find_set(y); if(heigh[x]==heigh[y]) { heigh[x]=heigh[y]+1; a[y]=x; } else if(heigh[x]<heigh[y]) a[x]=y; else a[y]=x; }查询优化——路径压缩
int find_set(int x) { if(x!=a[x]) a[x]=find_set(a[x]); return a[x]; }