• 作用：求连通分支数
    • 构成：
      • 整形数组 pre[]：记录每个节点的前向导点
      • find() 函数：查找
      • join() 函数：合并

    • find() 函数：对于每个点查找其上级

      1. int find(int x){
      2.  while(pre[x] != x){        //上级为自己就是最高级了
      3.      x = pre[x];
      4.  }
      5.  return x;
      6. }

    • join() 函数：合并两个连通分支

      1. void join(int x,int y){
      2.  int fx = find(x), fy = find(y);
      3.  if(fx != fy){
      4.      pre[fx] = fy;
      5.  }
      6. }

    • 路径压缩法：将 x 到根节点路径上的所有点的 pre（上级） 都设为根节点

      1. int find_pre(int x){
      2.  if(pre[x] == x){
      3.      return x;
      4.  }
      5.  return pre[x] = find_pre(pre[x]);
      6. }

    • 加权标记法：给每个节点标记树的深度，合并后不产生树退化（左右子树的深度差尽可能小），维护一个 rank[x] 数组，用以表达树 x 的深度，合并时，若 rank[x] < rank[y] ，令 pre[x] = y，否则相反

      1. void union(int i,int j){
      2.  i = find_pre(i);
      3.  j = find_pre(j);
      4.  if(i == j){
      5.      return;
      6.  }
      7.  if(rank[i] > rank[j]){
      8.      pre[j] = i;
      9.  }else{
      10.      if(rank[i] == rank[j]){
      11.          rank[j]++;
      12.      }
      13.      pre[i] = j;
      14.  }
      15. }

    • 模板

      1. class UnionFind{
      2.  int[] parent;                // parent[i]表示i这个元素指向的父亲节点
      3.  int[] size;                    //size[i]表示以i为根节点的集合中元素个数
      4.  int n;                        //节点的个数，初始化每一个节点都是一个单独的连通分量
      5.  int setCount;                //连通分量的数目
      7.  public UnionFind(int n){
      8.      this.size=new int[n];
      9.      this.parent=new int[n];
      10.      this.n=n;
      11.      this.setCount=n;
      12.      Arrays.fill(size,1);
      13.      for(int i=0;i<n;i++){
      14.          parent[i]=i;
      15.      }
      16.  }
      18.  public int find(int x){
      19.      return parent[x]==x?x:find(parent[x]);
      20.  }
      22.  public boolean unit(int x,int y){
      23.      x=find(x);
      24.      y=find(y);
      25.      if(x==y){
      26.          return false;
      27.      }
      28.      if(size[x]<size[y]){
      29.          int tem=x;
      30.          x=y;
      31.          y=tem;
      32.      }
      34.      parent[y]=x;
      35.      size[x]+=size[y];
      36.      --setCount;
      37.      return true;
      38.  }
      40.  public boolean connected(int x, int y) {
      41.      x = find(x);
      42.      y = find(y);
      43.      return x == y;
      44.  }
      45. }