并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

示例说明

如图所示，初始时各个结点都是单个独立的，随着一个个要求，结点之间进行了关联，最终变成若干各个树装的结构。这样可以清楚的看出那个结点是与什么结点是关联的，是在那一个数装结构中。

具体实现

从上图可以看出，各个结点随着要求进行关联最终是若干个树状类型的结构，想要对该结构进行操作则是对该结点的父节点属性进行操作。因为，一方面各个结点进行关联是最终要有相同的父节点，另一方面我们最终要实现的应用是判断两个结点是否有关联。所以目的是要找出这两个结点是否有同一个父节点。

初始化

可以定义一个数组或是哈希表来存储各个结点的父节点，这边以数组parent存储为例，数组的下标是指对应的结点，数组中的值是对应结点的父节点，及parent[i]表示i的父节点 初始时各个结点的父节点是其本身

private:
      vector<int> parent;
public:
      UnionFind(){
            parent.resize(7);
            iota(parent.begin(),parent.end(),0); // 进行初始化各个结点的父节点是其本身
      }

查询根节点

每个结点不断的寻找自己的父节点，若父节点是自己那么返回该点

• 路径压缩：查询时，树的高度决定了查询到根结点的速度，以上面的情况为例，若是关联要求变成a-b,b-c,c-d,e-f,f-g,d-e那么所组成的结构是高度为6的树，这在查询的速度上大打折扣。所以要对其进行相应的优化，在并查集的情况下，只要关心的是各个结点之间的连通性，而不要注意结点之间的距离，而且最终的目的是判断两个结点的根结点是否相同，所以可以对树的高度进行压缩优化，路径压缩有完全压缩和隔代压缩
  • 隔代压缩
    
    如图所示，通过将元素的父节点设置成元素原本父节点的父节点来不断的压缩树的高度

    int findRoot(int index){
       while(index!=parent[index]){
        parent[index] = parent[parent[index]];
        index = parent[index];
       }
       return index;
    }
    

  • 完全压缩
    
    如图所示，将树状结构变换成所有节点的父节点都指向根节点的星状结构

    int findRoot(int index){
        if (index == parent[index])
        return index;
        parent[index] = findRoot(parent[index]);
        return parent[index];
    }
    

合并

将相关联的两个结点的集合合并，就是将一个结点所在集合的根节点指向该结点，也就是说Root[a] = b。

void unionSet(int index1, int index2){
      parent[findRoot(index1)] = findRoot(index2);
}

完整代码示例

class UnionFind{
    private:
    vector<int> parent;
    public:
    UnionFind(){
        parent.resize(26);
        iota(parent.begin(),parent.end(),0);
    }
    int findParentIndex(int index){
        if (index == parent[index])
        return index;
        parent[index] = findParentIndex(parent[index]);
        return parent[index];
    }
    void unionSet( int index1, int index2){
        parent[findParentIndex(index1)] = findParentIndex(index2);
    }
};

例题

LeetCode——990. 等式方程的可满足性

• 问题描述
  给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b是小写字母（不一定不同），表示单字母变量名。
  只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

• 示例

  输入：["a==b","b!=a"]
  输出：false
  解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

  输出：["b==a","a==b"]
  输入：true
  解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

  输入：["b==b","b==c","a==c"]
  输出：true

• 提示

  1. 1<= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '='，要么是 '!'
  5. equations[i][2] 是 '='

• 代码实现

   class UnionFind{
   private:
      vector<int> parent;
   public:
      UnionFind(){
          parent.resize(26);
          iota(parent.begin(),parent.end(),0);
      }
      int findParentIndex(int index){
          if (index == parent[index])
          return index;
          parent[index] = findParentIndex(parent[index]);
          return parent[index];
      }
      void unionSet( int index1, int index2){
          parent[findParentIndex(index1)] = findParentIndex(index2);
      }
   };
  
   class Solution {
   public:
      bool equationsPossible(vector<string>& equations) {
          UnionFind uf;
          for(const string& str :equations){
              if (str[1]== '='){
                  int index1 = str[0] - 'a';
                  int index2 = str[3] - 'a';
                   uf.unionSet(index1,index2);
  
              }
  
          }
          for(const string& str: equations){
                    if (str[1]== '!'){
                  int index1 = str[0] - 'a';
                  int index2 = str[3] - 'a';
                  if (uf.findParentIndex(index1) == uf.findParentIndex(index2)){
                    return false;
                  }
              }
          }
          return true;
      }
   };
  

例题练习

• LeetCode——547：朋友圈
• LeetCode——200：岛屿数量
• LeetCode——684：冗余连接
• LeetCode——1319：连通网络的操作次数
• LeetCode——399：除法求值（中等）
• LeetCode——952：按公因数计算最大组件大小