• 概述
• 参考链接：
• 刷题
  • 入门题： 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. 省份数量（朋友圈）

1. dfs

2. bfs

3. 并查集

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_困难）