每天都刷朋友圈，那你知道并查集吗？

微信大概是我们每天必须接触的一个APP之一，公交上、地铁上、工作休息时，刷刷朋友圈，看看好友当天经历了什么。相较于QQ，微信的一个特点之一就是：除非好友的好友也是你的好友，否则你在朋友圈里看不到好友的好友对好友朋友圈的点赞和评论。

LeetCode上，有一道名为“朋友圈”的题目：

不过题目的要求和微信朋友圈不一样。题目说明，如果A和B是朋友，B和C是朋友，那么A和C也是朋友，即朋友圈中的友谊具有传递性。这里的朋友圈也就是朋友的集合。

如何来求解这个题目呢？那就要用到一个用于表示集合内元素关系的数据结构——并查集。

并查集

并查集是一种处理不相交集合的合并及查询问题的数据结构。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法等。换言之，并查集是一种树形结构，可以用来回答两个元素是否连接的问题。即，通过并查集算法，可以将两个不相连的元素连接起来，也可以查询两个元素是否已连接。这里的“连接”的含义是，两个元素是否具有同一个“根”（从这个角度可以理解，为什么是树形结构）。

并查集算法接口

并查集算法通常有以下几个接口：

• 查询两个元素是否连通：bool connected(int p, int q)
• 将给定的两个元素连通：void unionElement(int p, int q)
• 返回给定集合中有多少个连通分量：int count()

判断两个元素p和q是否连通，即判断元素p和q是否拥有同一个根root，这里我们需要实现一个辅助函数find(int p)，用于查找元素p的根。同理，将两个元素连通，只需要保证两个元素的根是同一个元素即可。

并查集算法代码

代码实现中，我们使用一个int型的数组parent来表示每一个元素的前驱元素是谁，即它的父节点是谁。如果将元素p和q连接起来了，可以说p是q的父节点，因此parent[q] = p。此时函数find(q)的结果也就是p了，也就是说，此时去寻找q元素的根节点，也就是p了。当然，也有可能p并不是根节点，因为p的根节点可能是m，即find(p)=m。所以find(q)的最终结果是m。（可以看到这里有迭代关系）。

下列是并查集算法的C++实现：

class UnionFind{
private:
  // 元素个数
  int n;

  // 每个元素的父节点
  int* parent;

  // 连通分量个数
  int ccount;
public:
  UnionFind(int n){
    this->n = n;

    // 初始时，每个元素都独立，所以有n个连通分量
    ccount = n;
    this->parent = new int[n];

    // 初始化每个元素的根节点是自己
    for (int i = 0; i < n; i++){
      parent[i] = i;
    }
  }
  ~UnionFind(){
    // 注意释放空间
    delete[]parent;
  }

  // 查找元素p的根
  int find(int p){
    while (p != parent[p]){
      p = parent[p];
    }
    return p;
  }
  // 判断两个元素是否连通，即是否具有同一个根
  bool connected(int p, int q){
    return find(p) == find(q);
  }

  // 将两个元素连通
  void unionElement(int p, int q){
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)return;
    parent[rootQ] = rootP;

    // 连通后，连通分量将减少1
    ccount--;
  }

  // 返回连通分量个数
  int count(){
    return ccount;
  }
};

可以看到，并查集这个高级的数据结构，其实代码实现很简单。不过，这部分代码有优化的空间，比如查找函数中，可以使用路径压缩。

路径压缩

假设有如下一个连通图，我们要查找元素7的根，最终要经过6次迭代查找，这样的查找效率是很低的（类似于退化为链表的二叉树）。

我们可以做一些优化：如果经过一次查找发现7的根并不是7，那么可以将7的父节点指向其父节点的父节点，如下图：

这样只需要经过3次迭代就可以找到最终的root了。这就是路径压缩。

路径压缩的代码如下：

// 查找元素p的根：路径压缩
  int find(int p){
    while (p != parent[p]){
      parent[p] = parent[parent[p];
      p = parent[p];
    }
    return p;
  }

求解朋友圈问题

再看看本文刚开始时提到的朋友圈问题，从示例给出的矩阵可以看到，这是一个对称矩阵，因此我们可以只考察左下或右上部分即可。如何考察呢？如果某个元素M[i][j]==1，说明i和j是好友，这时候只需要使用union将二者连接起来即可。

该题目求最后有几个朋友圈，其实也就是求有几个连通分量。由并查集的上述代码实现可知，初始化时，连通分量个数被初始化为元素个数，每当成功执行一次合并操作后，连通分量个数减1。所以最后我们直接返回count函数即可。

int findCircleNum(vector<vector<int>>& M) {
        int num = M.size();
        UnionFind uf(num);
        for(int i=0;i<num;i++){
            for(int j = i+1;j<num;j++){
                if(M[i][j] == 1 && !uf.connected(i,j)){
                    uf.unionElement(i,j);
                }
            }
        }
        return uf.count();
    }

更多关于并查集的题目和应用

LeetCode上还有更多可以使用并查集来求解的题目。比如：

• 130.被包围的区域
• 200.岛屿数量
• 684.多余连接
• ……

并查集在图论中还有更强大的应用，使用并查集可以高效地判断图中是否有环，计算一个图的连通分量等等。比如我们一开始提到的Kruskal算法。Kruskal算法是用于求解最小生成树问题的一个经典算法。（关于最小生成树和Kruskal算法，之后再细说）。这里说下，Kruskal算法中是如何利用并查集来判断图中是否有环的？

比如下图的例子，在这样一个图中，如果我们把8和2进行union操作，将会形成一个环8-9-6-2-8。根据Kruskal算法，最小生成树中是不能有环的。如何判断呢？

如果find(2)和find(8)得到的是同一个root，上图的root是10，那说明其实2和8已经连通了，如果再次连通，必将形成一个环。这个判断过程其实就是并查集的接口connect的实现过程：

// 声明一个对象
UnionFind uf(n);

// Do something

// 判断p和q是否已经连通
if (uf.connected(p, q){
  // 已经连通，则返回
  return;
}

// 如果没有连通，则将两个元素连通
uf.unionElements(p, q);

// Do something

怎么样，并查集是不是很神奇？