| 并查集 | 路径压缩 |
这是一道典型的并查集问题，本次贴了多种计算种类数的方法，希望能够加深理解
#include<iostream>
#include<algorithm>
#include<string>
#include<set>using namespace std;int n,m;
int p[50010];int find(int x){if(p[x]==x){return x;}p[x] = find(p[x]);return p[x];
}void merge(int x,int y){int rx = find(x);int ry = find(y);if(rx!=ry){p[ry] = rx;}
}int main(){int t=1;while(cin>>n>>m){if(n==0&&m==0){break;}for(int i=1;i<=n;i++){p[i] = i;}int x,y;for(int i=1;i<=m;i++){cin>>x>>y;merge(x,y);}set<int>s;for(int i=1;i<=n;i++){s.insert(find(i)); //注意这里是find}int res = s.size();printf("Case %d: %d\n",t,res);t++;}return 0;
}
种类计算方法2：
for (int i = 0; i < n; i++) {if (parent[i] == i) { // 判断是否为根count++;}
}