并查集

1.并查集原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于统一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集union-find set。比如某公司今年校招全国总招生10人西安招4人成都招3人武汉招3人10个人来自不同的学校起先互不认识每个学生都是一个独立的小团体现给这些学生进行编号{1,2,3,4,5,6,7,8,9}给以下数组用来存储该小集体数组中的数字代表该小集合中具有成员的个数。毕业后学生们要去公司上班每个地方的学生自发组织成小分队一起上路于是西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个人形成了三个小团体假设0,1,2分别担任队长负责大家的出行。一趟火车之旅后每个小分队成员就互相熟悉成为一个朋友圈从上图可以看出编号6,7,8同学属于0号小分队该小分队中有4人包含队长0编号4和9的同学属于1号小分队该小分队有3人包含队长1编号为3和5的同学属于2号小分队该小分队有3人包含队长2。仔细观察数组内情况可以得出以下结论数组的下标对应集合元素的编号。数组中如果为负数负数代表根数字代表该集合中元素个数数组中如果为非负数代表该元素双亲在数组中的下标。在公司工作一段时间后西安小分队中8号同学与成都小分队1号同学奇迹的走在了一起两个小圈子的学生相互介绍最后成为了一个小圈子现在0集合有7个人2集合有3个人总共两个朋友圈。通过以上例子可知并查集一般可以解决以下问题1.查找元素属于那个集合沿着数组表示树形关系以上一直找到根树中元素为负数的位置2.查看两个元素是否属于同一个集合沿着数字表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在3.将两个集合归并成一个集合将两个集合中的元素合并将一个集合名称改成另一个集合的名称。4.集合的个数遍历数组数组中元素为负数的个数即为集合的个数。2. 并查集的模拟实现#pragma once #includeiostream #includevector using namespace std; class UnionFind { public: UnionFind(int n) : _v(n, -1) //用n个数初始化 {} int FindRoot(int index) { int root x; while (_v[root] 0) { root _v[root];//数组中存的就是当前数的父亲节点 } //路径压缩 while(_v[x] 0) { int parent _v[x]; _v[x] root; x parent; } return root; } void Union(int x1, int x2)//合并 { int root1 FindRoot(x1); int root2 FindRoot(x2); if(root1 root2) return; if(abs(_v[root1]) abs(_v[root2])) //控制数据量小的往大的集合合并 { swap(root1, root2); } _v[root1] _v[root2]; //根节点加等上当前节点的值 _v[root2] root1; //当前节点的值指向父亲 } size_t SetCount()//有多少棵树 { size_t count 0; for (size_t i 0; i _v.size(); i) { if (_v[i] 0) count; } return count; } private: vectorint _v; };3.与并查集相关的题LCR 116. 省份数量 - 力扣LeetCodeclass UnionFind { public: UnionFind(int n) : _v(n, -1) //用n个数初始化 {} int FindRoot(int index) { while (_v[index] 0) { index _v[index];//数组中存的就是当前数的父亲节点 } return index; } void Union(int x1, int x2) { int root1 FindRoot(x1); int root2 FindRoot(x2); if (root1 ! root2) { _v[root1] _v[root2]; //根节点加等上当前节点的值 _v[root2] root1; //当前节点的值指向父亲 } } size_t SetCount()//有多少棵树 { size_t count 0; for (size_t i 0; i _v.size(); i) { if (_v[i] 0) count; } return count; } private: vectorint _v; }; class Solution { public: int findCircleNum(vectorvectorint isConnected) { UnionFind u(isConnected.size()); for(int i 0; i isConnected.size(); i) { for(int j 0; j isConnected[0].size(); j) { if(isConnected[i][j] 1) { u.Union(i, j);//相连就合并这两个城市 } } } return u.SetCount(); } };990. 等式方程的可满足性 - 力扣LeetCode下面使用并查集第一次循环先把所有的树给找到然后第二次循环判断它们是否在同一个树里面。class Solution { public: bool equationsPossible(vectorstring equations) { vectorint ufs(26, -1); auto findroot [ufs](int x) { while(ufs[x] 0) x ufs[x]; return x; }; for(int i 0; i equations.size(); i) { if(equations[i][1] ) { int root1 findroot(equations[i][0] - a); int root2 findroot(equations[i][3] - a); if(root1 ! root2) { ufs[root1] ufs[root2]; ufs[root2] root1; } } } for(int i 0; i equations.size(); i) { if(equations[i][1] !) { int root1 findroot(equations[i][0] - a); int root2 findroot(equations[i][3] - a); if(root1 root2) { return false; } } } return true; } };