算法动画秒懂并查集
并查集是一种很常用的数据结构，LeetCode上面有二十多道题，这次我们来看一道入门题目LeetCode 547 省份数量。
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
题意解读
给定一个对称矩阵，表示城市之间的连通关系，1表示连通0表示不连通。n个城市通过这个关系划分为多棵树，每棵树表示一个省，我们需要求出省的数量。
并查集
并查集能很好的处理这种集合关系，和朋友圈类似，比如有n个人，需要将这些人划分到不同的圈子。并查集有两个操作，一个是find，也就是查找这个人属于哪个圈子，另一个是union，是合并圈子。
并查集初始的时候每个人都是一个圈子，每个人的圈子都指向自己，每次union合并操作，会把一个圈子a的根节点指向另一个圈子b的根节点，这样圈子a的所有节点的根节点也会跟着指向圈子b的根节点，达到合并的目的。
并查集的压缩处理是在find的过程中记录每个节点所在圈子的根节点，这样不需要递归遍历查询。
一秒记忆
一句话：合并是一个根节点指向另一个根节点，一山不容二虎。
动画题解
根据本题的数据和题解，制作了专门的动画题解
源代码
class Solution {
public:
// 寻找树根
int Find(vector<int>& root, int index) {
if (root[index] != index) {
root[index] = Find(root, root[index]);
}
return root[index];
}
// 将一个根节点指向另一个根节点
void Union(vector<int>& root, int index1, int index2) {
root[Find(root, index1)] = Find(root, index2);
}
int findCircleNum(vector<vector<int>>& isConnected) {
int size = isConnected.size();
vector<int> root(size);
// 初始指向自己
for (int i = 0; i < size; i++) {
root[i] = i;
}
//合并集合
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (isConnected[i][j] == 1) {
Union(root, i, j);
}
}
}
//计算树的个数
int circles = 0;
for (int i = 0; i < size; i++) {
if (root[i] == i) {
circles++;
}
}
return circles;
}
};
总结
并查集解决的是集合快速查询和合并的问题，数据集就是图，每个模块都是一颗树，合并的时候其实就是将一个树根指向另一个树根，查找操作就是查找节点所在树的根节点。这样理解不容易出错，也很清晰。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
