C语言刷leetcode——并查集
- 概述
- 参考链接：
- 刷题
- 入门题： 547. 省份数量（朋友圈）
- 684. 冗余连接
概述
https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/
基本概念
并查集是一种数据结构
并查集这三个字，一个字代表一个意思。
并（Union），代表合并
查（Find），代表查找
集（Set），代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素
并查集的典型应用是有关连通分量的问题
并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)O(1)
因此，并查集可以应用到在线算法中
参考链接：
https://zhuanlan.zhihu.com/p/417587917
https://blog.csdn.net/weixin_54186646/article/details/124477838
刷题
入门题： 547. 省份数量（朋友圈）
-
dfs
-
bfs
-
并查集
int Find(int* parent, int index) {
if (parent[index] != index) {
parent[index] = Find(parent, parent[index]);
}
return parent[index];
}
void Union(int* parent, int index1, int index2) {
parent[Find(parent, index1)] = Find(parent, index2);
}
int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize) {
int cities = isConnectedSize;
int parent[cities];
for (int i = 0; i < cities; i++) {
parent[i] = i;
}
for (int i = 0; i < cities; i++) {
for (int j = i + 1; j < cities; j++) {
if (isConnected[i][j] == 1) {
Union(parent, i, j);
}
}
}
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (parent[i] == i) {
provinces++;
}
}
return provinces;
}
684. 冗余连接
2.3.1 朋友圈的参考解法（547）
2.3.2 冗余连接（684）
2.3.3 岛屿数量（200_必做）
https://leetcode.cn/problems/number-of-islands/solution/cyu-yan-bing-cha-ji-mo-ban-jian-yi-bei-xia-lai-by-/
2.3.4 句子相似性II (737_会员)
2.3.5 得分最高的路径（1102_会员）
2.3.6 最低成本联通所有城市（1135_会员）
2.3.7 以图辨树（261_会员）
2.3.8 按字典序排列最小的等效字符串（1061_会员）
2.3.9 无向图中连通分量的数目（323_会员）
2.3.10 尽量减少恶意软件的传播（924_困难）