这是我写的第一道并查集的题，也应该是一道最简单的入门题了，所以就以这道题说下并查集，其实就是找关系，比如说这道题的题意就是有n个人聚餐，然后他们不一定都互相认识，如果a认识b，b认识c，那么就让他们仨坐一桌，再如果c认识d，d认识e，那么就让这三个人另外坐一桌，所以就是有关系的就坐一桌，然后问需要多少张桌子(忽略每张桌子能坐多少人)。 

       那么并查集就分为并和查两个过程， 首先我们需要开一个数组pre来记录，刚开始我们初始化为pre[i] = i，然后在输入数据的时候将他们有关系的都并起来，比如输入1和2，2和3，我们可以先查这些点的是不是独立的结点，如果是的话就把他们连起来，那么就是pre[2]=1,pre[3]=2，这里可以用一个路径压缩，来把3号的父节点改成1，这样更便于查找(压缩路径下面会说)，那么现在就是pre[2]=1,pre[3]=1，这就是并的过程，而查的过程就是比如说你要查3号，然后pre[3]就是3号对应的根节点了。思路大概是这样的，具体的东西可以结合代码看一下。

       并查集呢也就是并和查两个部分，所以用两个函数Merge和Find(我习惯这么定义了)，而查的过程中有很多种写法，可以用循环，也可以用递归，我看其他Dalao的博客写的都很详细，我也没有那么好的文采，所以这里就不详细的说了。先说一下没有路径压缩的写法，虽然路径压缩可以大大减短运行时间，但是有时候有些题它不压缩路径才能做。思路就是在一个while循环里不断的去查当前节点的父节点，直到x==pre[x]为止，最后的r就是你要查的x的根节点了。

int Find(int x){ 
  int r=x; 
  while(parent[r] !=r) 
     r=parent[r];
  return r; 
}

       然后说一下路径压缩的方法，路径压缩可以缩短程序运行时间，方法也分为递归方法和非递归方法，而递归方法有时候对于数据较大的程序来说会造成栈溢出，所以对于这种情况可以用非递归的方法，不太好理解，试着手动模拟一下就很好理解了。 

int Find(int x){              // 非递归方法
    int k, j, r;
    r = x;
    while(r != parent[r])     // 查找跟节点
        r = parent[r];        // 找到跟节点，用r记录下
    k = x;
    while(k != r){
        j = parent[k];         // 用j暂存parent[k]的父节点
        parent[k] = r;        // parent[x]指向跟节点
        k = j;                    // k移到父节点
    }
    return r;
}
 
int Find(int x){                   // 递归方法
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

     然后是并的过程。 

void merge(int x,int y){
  int fx = Find(x);         // 查找x的根节点
  int fy = Find(y);         // 查找y的根节点
  if(fx != fy){
    pre[fy] = fx;           // 合并
  }
}

      最后看一下开头说的那道题的代码吧，还不理解的就手动模拟一下。 

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1005;
int pre[MAXN];
int T,n,m;
 
void init(){
  for(int i=0;i<=n;i++){
    pre[i] = i;
  }
}
 
int Find(int x){
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}
 
void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
  }
}
 
int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
      int a,b;
      scanf("%d%d",&a,&b);
      merge(a,b);
    }
    int sum = 0;
    for(int i=1;i<=n;i++){
      if(i == pre[i]){
        sum++;
      }
    }
    printf("%d\n",sum);
  }
  return 0;
}