How many tables

并查集

#include<iostream>

using namespace std;
const int N = 1050;
int s[N];
void init_set(){                           //初始化
  for(int i = 1; i <= N; i++) s[i] = i;    //元素值与下标一致，独立的集
}
int find_set(int x){                       //查找
  return x==s[x]? x:find_set(s[x]);        //递归找到根节点的集
}
void merge_set(int x, int y){              //合并
  x = find_set(x); y = find_set(y);
  if(x != y) s[x] = s[y];                  //把x合并到y上，y的根成为x的根
}
int main (){
  int t, n, m, x, y; cin >> t;             //t个测试
  while(t--){
    cin >> n >> m;                         //朋友人数、关系表行数
    init_set();
    for(int i = 1; i <= m; i++){
      cin >> x >> y;
      merge_set(x, y);                     //合并x和y
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)            //统计有多少个集
      if(s[i] == i) ans++;
    cout << ans <<endl;
  }
  return 0;
}

笔记：并查集的基本操作：1、初始化：每个元素都是独立的集。2、合并：将有朋友关系的节点合并到一起。3、查找：元素的根节点的集。4、统计：统计根节点（集）的数量

并查集（优化）

#include<iostream>

using namespace std;
const int N = 1050;
int s[N];
int height[N];
void init_set(){
  for(int i = 1; i <= N; i++){
    s[i] = i;
    height[i] = 0;                       //树的高度
  }
}
int find_set(int x){
  return x==s[x]? x:find_set(s[x]);
}
void merge_set(int x, int y){            //优化合并操作
  x = find_set(x); y = find_set(y);
  if( height[x] == height[y]){
    height[x] = height[x] + 1;          //合并，树的高度+1
    s[y] = x;
  }
  else{                                 //把矮树合并到高树上，高树的高度保持不变
    if (height[x] < height[y]) s[x] = y;
    else s[y] = x;
  }
}
int main (){
  int t, n, m, x, y; cin >> t;
  while(t--){
    cin >> n >> m;
    init_set();
    for(int i = 1; i <= m; i++){
      cin >> x >> y;
      merge_set(x, y);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
      if(s[i] == i) ans++;
    cout << ans <<endl;
  }
  return 0;
}

笔记：优化并查集的合并部分，将短的根节点放到长的根节点上，能减少树的长度，减少搜索深度