并查集

并查集是什么

并查集是一种用于处理动态连通性问题的数据结构。

并查集提供了有效的方法来合并和查询元素之间的连接关系，例如判断图中的连通分量，处理网络连接，解决社交网络中的朋友关系

并查集可以查询节点的根是否相同来判断两个节点是否处于同一个连通区

并查集的基本原理

并查集的核心思想是将一组元素分成 若干个不相交的集合，并支持以下两种基本操作：

1. 查找：确定某个元素属于哪个集合，这个操作通常返回一个代表该元素的根元素
2. 合并：将两个集合合并为一个集合

并查集的数据结构

并查集通常用两个数组来实现

1. parent数组：parent[i]表示元素i的父节点，如果parent[i] = i ，则i是集合的根节点
2. rank数组：用于优化合并操作，表示树的高度。通过将较矮的树合并到较高的树下，可以保持树的平衡，从而提高效率

并查集的主要操作

1. 查找操作（Find）

   查找某个元素的根节点，如果元素不是根节点，则递归查找其父节点，直到找到根节点

   为了提高效率，可以使用路径压缩（Path Compression）技术：在查找的过程中，将访问到的所有节点直接连接到根节点，从而压缩路径

   int find(int x)
   {
      if(parent[x] != x)
      {
          parent[x] = find(parent[x]);//路径压缩
      }
      return parent[x];
   }

2. 合并操作（Union）

   将两个集合合并，首先找到两个元素的根节点，如果他们的根节点不同，则将其中一个根节点的父节点指向另一个根节点

   为了优化合并操作，可以使用按秩合并策略：将较低秩的树合并到较高秩的树下，从而避免树的高度过高

   void union(int x , int y)
   {
      int rootX = find(x);
      int rootY = find(y);
      if(rootX != rootY)
      {
          if(rank[rootX] > rank[rootY])
          {
              parent[rootY] = rootX;
          }else if(rank[rootX] < rank[rootY])
          {
              parent[rootX] = rootY;
          }else{
              parent[rootY] = rootX;
              rank[rootX]++;
          }
      }
   }

并查集其他操作

1. 初始化

   vector father(n,0);
   void init(int n){
      for(int i = 0 ; i < n ; i++) father[i] = i; 
   }

2. 判断是否处于相同连通区

   bool isSame(int u , int v)
   {
      u = find(u);
      v = find(v);
      return u == v;
   }

3. 将v->u这条边加入

   void join(int v , int u)
   {
      v = find(v);
      u = find(u);
      if(v == u) return;
      father[v] = u;
   }

例题

冗余连接

并查集的封装

class UnionFind{
public:
    UnionFind(int n)
    {
        parent.resize(n,0);
        rank.resize(n,0);
        for(int i = 0 ; i < n ; i ++) parent[i] = i;
    }
    int find(int x)
    {
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    bool unionSets(int u , int v){
        int rootu = find(u);
        int rootv = find(v);
        if(rootu != rootv)
        {
            if(rank[rootu] < rank[rootv])
            {
                parent[rootu] = rootv;
            }else if(rank[rootu] > rank[rootv])
            {
                parent[rootv] = rootu;
            }else{
                parent[rootv] = rootu;
                rank[rootu]++;
            }
            return true;
        }
        return false;
    }
private:
    vector<int> parent;
    vector<int> rank;
};