并查集详解

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in life并查集一句话概括用来管理一堆不相交集合支持「找元素属于哪个集合」和「合并两个集合」的数据结构就像管理朋友圈、连通块核心思想用数组存森林多棵树数组parent[]有两条规则如果parent[x] 0x 是这棵树的根负数的绝对值 当前集合里元素总数。如果parent[x] 0parent [x] 是 x 的父节点编号顺着一直往上找直到找到负数就是这个集合的根。两大基础操作1. find (x) —— 查找 x 所在集合的根功能找到元素x的根节点判断两个元素是否在同一个集合只需要看它们find出来的根是否一样。 优化路径压缩递归 / 迭代查找的时候把沿途所有节点直接连到根上减少后续查找时间2. union (x,y) —— 合并 x 和 y 所在的两个集合功能把 x 所在集合 和 y 所在集合合并成一个集合。 优化按大小合并按秩合并小集合合并到大集合下面避免树变得很高保证效率。步骤root_x find(x)root_y find(y)如果root_x root_y本来就在一个集合不用合并否则把更小的树挂到大树的根下面更新大树根的集合大小。例子理解1.初始10 个人10 个集合数组全-12.分组s1{0,6,7,8}根 0parent[0]-4678一共3个-1相加到0s2{1,4,9}根 1parent[1]-3s3{2,3,5}根 2parent[2]-3数组[-4,-3,-3,2,1,2,0,0,0,1]3.合并 8 号和 1 号find函数找某个节点的根find(8)0find(1)1本身自己就是根所以二者不属于同一集合就可以把集合 1 并入集合 0parent[0] -4 (-3) -7parent[1]0数组变成[-7,0,-3,2,1,2,0,0,0,1]现在一共 2 个集合大小分别 7、3。为什么要小的集合合并到大的集合简单举个例子来看A集合有2个元素B集合有1个元素如果A合并到B那么就会形成D一共有3层如果是B合并到A那么就只有2层。所以小树合并到大树下面是为了不让树变高。树越矮find 查找的时候走的层数越少速度越快。一步步实现并查集构造函数全部初始化为-1FindRoot1迭代版eg2递归版FindRoot(_ufs[x])递归去找 x 父节点的根找到根之后赋值给_ufs[x]把 x 的父节点直接改成根返回这个根。这一步就是路径压缩递归回溯的时候把沿途所有节点直接挂到根上。eg:假设_ufs[3]2_ufs[2]1_ufs[1]-4找 FindRoot (3)_ufs [3]20递归 FindRoot (2)_ufs [2]10递归 FindRoot (1)_ufs [1]-4 0 → 返回根 1回到上一层_ufs[2] 1返回 1回到最外层_ufs[3] 1返回 1执行完后_ufs[3]1_ufs[2]13、2 都直接指向根 1路径压缩完成。UnionCount()统计一共有多少个根即一共有多少个集合2道并查集题1.省份数量初始化并查集n 个城市每个城市父节点初始是自己。遍历邻接矩阵 只要isConnected[i][j]1就把城市 i 和城市 j 合并。统计根遍历所有城市数有多少个parent[i]i就是答案。class Solution { public: vectorintufs; int find(int x) { if(ufs[x]0)return x; return ufs[x]find(ufs[x]); } int findCircleNum(vectorvectorint isConnected) { int nisConnected.size();//n x n ufs.resize(n,-1); int count0; for(int i0;in;i) { for(int j0;jn;j) { if(isConnected[i][j]1) { int root1find(i); int root2find(j); if(root1!root2) { if(abs(ufs[root1])abs(ufs[root2])) { swap(root1,root2); } ufs[root2]ufs[root1]; ufs[root1]root2; } } } } for(int i0;iufs.size();i) { if(ufs[i]0)count; } return count; } };2.等式方程的可满足性先遍历所有等式方程把相等的字母合并到同一集合再遍历所有不等式方程检查如果不等的两个字母已经在同一个集合 (说明是相等的→ 矛盾返回 false全部不等式校验通过返回 true。class Solution { public: vectorintufs; int find(int x) { if(ufs[x]0)return x; return ufs[x]find(ufs[x]); } void Union(int x,int y) { int root1find(x); int root2find(y); if(root1root2)return; if(ufs[root1]ufs[root2]) { swap(root1,root2); } ufs[root2]ufs[root1]; ufs[root1]root2; } bool equationsPossible(vectorstring equations) { ufs.resize(26,-1); for(int i0;iequations.size();i) { if(equations[i][1]) { Union(equations[i][0]-a,equations[i][3]-a); } } for(int i0;iequations.size();i) { if(equations[i][1]!) { if(find(equations[i][0]-a)find(equations[i][3]-a))return false; } } return true; } };