输入一些整数，给出若干个一对的信息，将其分为几组，返回组的数量

思路

  1. 先写初始化函数，每个结点的爸爸都是自己
  2. 写合并函数，如果结点的根不同就合并
  3. 写归一化根结点函数，将同一个组的结点父亲全部统一
  4. 用isRoot数组计算组数
  5. 最后直接加bool变量就行

PS：如果需要统计每组人数，将isRoot改成int型即可

代码

  1. #include<algorithm>
  2. #include<vector>
  3. #include<iostream>
  4. using namespace std;
  6. const int maxn = 110;
  7. int m, n;
  8. int father[maxn];
  9. int isRoot[maxn];
  10. int find_father(int i){
  11.     if(father[i] == i) return i;
  12.     else{
  13.         int f = find_father(father[i]);
  14.         father[i] = f;
  15.         return f;
  16.     }
  17. }
  19. void Union(int a, int b){
  20.     int faA = find_father(a);
  21.     int faB = find_father(b);
  22.     if(faA!=faB) father[faA] = faB;
  23. }
  25. int main(){
  26.     scanf("%d%d", &n, &m);
  27.     int node1, node2;
  28.     for(int i = 1; i <= n; i++) {
  29.         father[i] = i;// 一开始自己都是自己的爸爸
  30.         isRoot[i] = false;
  31.     }
  32.     for(int i = 0; i < m; i++){
  33.         scanf("%d%d", &node1, &node2);
  34.         Union(node1, node2);
  35.     }
  36.     //初始化根结点
  37.     for(int i = 1; i <= n; i++){
  38.         isRoot[find_father(i)] = true;
  39.     }
  40.     int count = 0;
  41.     for(int i = 1; i <= n; i++){
  42.         count += isRoot[i];
  43.     }
  44.     printf("%d",count);
  45.     return 0;
  46. }