目录

一、并查集原理

二、并查集实现

三、并查集应用

547. 省份数量 - 力扣（LeetCode）

总结

一、并查集原理

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-fifind-set)。

通俗的来说就是找朋友问题

假如现在有10个人，分别是{0，1，2，3，4，5，6，7，8，9}

他们有些人之间是朋友，现在将他们按照朋友圈划分为几个小集合

有一天7和4成为了好朋友，那么就需要将左侧两个朋友圈合并成为一个朋友圈

这就是并查集要解决的问题

并查集实际上是一个森林，它是由多棵树构成的

我们这里采用的表示树的方法与之前的二叉树不同，类似于堆，利用数组下标来确定父子关系

初始条件，每一个位置都是-1，代表每一个人都是一个小集合

然后合并朋友圈

二、并查集实现

并查集的主要接口就只有两个Union和FindRoot

首先来说FindRoot

寻找根节点，什么属于根节点呢？

数组中存储的是负数的下标就是根的位置，这句话有一点绕

我们要找根节点，就是找数组不为负数的位置

    size_t FindRoot(int x){if(x < 0 || x >= _set.size()){throw invalid_argument("非法参数");return -1;}size_t parent = x;while(_set[parent] >= 0){parent = _set[parent];}return parent;}

有了FindRoot的基础之后Union，就容易理解了

Union是将两个集合合并，我们只要两个参数就可以x1,x2

我们先分别查找x1和x2的父亲，如果他们是同一个父亲，就不需要合并，如果他们的父亲不同，就将他们合并。

合并也十分简单

我们直接将x2父亲加到x1父亲上，并且将x2的父亲更改为x1的父亲

    void Union(int x1, int x2){size_t root1 = FindRoot(x1);size_t root2 = FindRoot(x2);_set[root1] += _set[root2];_set[root2] = root1;}

最后一个接口是SetCount，是用来计算并查集现在有几个集合的，也就是有几棵树

很简单，遇到数组中的负数，计数器就自增

    size_t SetSize(){size_t size = 0;for(const auto& e : _set){if(e < 0){size++;}}return size;}

完整代码：

#pragma once
#include 
#include 
#include 
using namespace std;class UnionFindSet
{
public:UnionFindSet(size_t n):_set(n, -1){}size_t FindRoot(int x){if(x < 0 || x >= _set.size()){throw invalid_argument("非法参数");return -1;}size_t parent = x;while(_set[parent] >= 0){parent = _set[parent];}return parent;}void Union(int x1, int x2){size_t root1 = FindRoot(x1);size_t root2 = FindRoot(x2);_set[root1] += _set[root2];_set[root2] = root1;}size_t SetSize(){size_t size = 0;for(const auto& e : _set){if(e < 0){size++;}}return size;}private:vector _set;
};

三、并查集应用

547. 省份数量 - 力扣（LeetCode）

这道题是典型的并查集应用，用来判断到底最后被划分为几个集合

class Solution {
public:int findCircleNum(vector>& isConnected) {vector ufs(isConnected.size(), -1);auto FindRoot = [&ufs](int x){while(ufs[x] >= 0){x = ufs[x];}return x;};for(size_t i = 0; i < isConnected.size(); i++){for(size_t j = 0; j < isConnected[i].size(); j++){if(isConnected[i][j] == 1){size_t root1 = FindRoot(i);size_t root2 = FindRoot(j);if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}}size_t ans = 0;for(size_t i = 0; i < ufs.size(); i++){if(ufs[i] < 0)ans++;}return ans;}
};

总结

以上就是今天要讲的内容，本文仅仅讲解了并查集的简单实现及应用