并查集算法的学习

并查集

一. 介绍

并查集一般用于无向图需要查询多个节点是否属于同一集合时使用，或者需要统计无向图每个点集的节点数量

二. 模板

class UnionFind {int[] parent;//每个节点的连通父节点int[] size;//每个节点拥有的子节点数public UnionFind(int n) {parent = new int[n];size = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;//初始化指向自己size[i] = 1;}}/** @description  寻找当前节点的祖先* @param: x* @returns int* @author yamu* @date 2025/5/9 10:39*/public int find(int x) {while (x != parent[x]) {parent[x] = find(parent[x]);x = parent[x];}return parent[x];}/** @description 合并两个集合* @param: x* @param: y* @returns void* @author yamu* @date 2025/5/9 10:38*/public void union(int x, int y) {int x_parent = find(x);int y_parent = find(y);//祖先不同才合并if (x_parent != y_parent) {//小的往大的合并if (size[x_parent] <= size[y_parent]) {parent[x_parent] = y_parent;size[y_parent] += size[x_parent];} else {parent[y_parent] = x_parent;size[x_parent] += size[y_parent];}}}
}

三. 题单

参考灵神题单

1. 547. 省份数量 - 力扣（LeetCode）
2. 1971. 寻找图中是否存在路径 - 力扣（LeetCode）
3. 2316. 统计无向图中无法互相到达点对数 - 力扣（LeetCode）
4. 1319. 连通网络的操作次数 - 力扣（LeetCode）
5. 924. 尽量减少恶意软件的传播 - 力扣（LeetCode）
6. 928. 尽量减少恶意软件的传播 II - 力扣（LeetCode）
7. 3108. 带权图里旅途的最小代价 - 力扣（LeetCode）

547 模板题
1971 模板题
2316 模板题
1319 模板题
924 好题，虚拟删除节点
928 好题，真正删除节点和节点边
3108 模板题，需要统计权值