Union-Find算法

• 基本概念
• • 并查集模板
  • • 1. [参考leetcode](https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/)
    • 2.平衡优化和重量优化

基本概念

• 并查集是一种数据结构
• 并查集这三个字，一个字代表一个意思。
  并（Union），代表合并
  查（Find），代表查找
  集（Set），代表这是一个以字典为基础的数据结构，它的基本功能是合并集合中的元素，查找集合中的元素
• 并查集的典型应用是有关连通分量的问题
• 并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)
• 因此，并查集可以应用到在线算法中

链接：https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/

并查集模板

1. 参考leetcode

class UnionFind{
public:// 查找祖先：如果节点的父节点不为空，那就不断迭代。int find(int x){int root = x;while(father[root] != -1){root = father[root];}// 路径压缩while(x != root){int original_father = father[x];father[x] = root;x = original_father;}return root;}// 判断两个节点的连通性bool is_connected(int x,int y){return find(x) == find(y);}// 合并两个节点：如果发现两个节点是连通的，// 那么就要把他们合并，也就是他们的祖先是相同的。// 这里究竟把谁当做父节点一般是没有区别的。void Union(int x,int y){int root_x = find(x);int root_y = find(y);if(root_x != root_y){father[root_x] = root_y;num_of_sets--;}}// 初始化：当把一个新节点添加到并查集中，它的父节点应该为空void add(int x){if(!father.count(x)){father[x] = -1;num_of_sets++;}}int get_num_of_sets(){return num_of_sets;}private:// 记录父节点unordered_map father;// 记录集合数量int num_of_sets = 0;
};

2.平衡优化和重量优化