上海学做网站,嘉兴做网站seo,企业网站的推广形式有哪些,专业网站开发公司地址并查集原理 在一些应用问题中#xff0c;需要将n个不同的元素划分成一些不相交的集合。开始时#xff0c;每个元素自成一个 单元素集合#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询一 个元素归属于那个集合的运算。适合于描述这类…并查集原理 在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个 单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询一 个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。 一般可以用数组来表示并查集数据的下标就是每个数据的编号对应的值如果是负数那么就代表它自成一个集合也就是一个根结点。如图初始值一般都是负数也就是每个元素都自成一个集合如果一个元素是根那么负数的绝对值则代表这个树有多少结点如果不是负数那么则说明这个元素不是根且对应的值存的是父亲结点的下标。 实际应用中也可以通过加入哈希表来设置更多的映射关系这样的话可以将数组的下标作为key值然后可以存人名这些。 所以并查集其实也是多棵树组成的森林。 用并查集表示就是 元素之间可以合并并且可以制定合并规则。集合与集合之间也可以合并。 综上我们可以知道并查集可以解决以下问题
1.查找某个元素属于哪个集合。沿着数组表示的树形关系向上可以一直找到根。
2.查看两个元素是否属于同一个集合。可以看找到的根是否相同以此来判断是否属于同一个集合。
3.可以将两个集合归并成一个集合。
4.求集合的个数。其实也就是根的个数可以遍历数组记录下标为负数的元素即是集合的个数。
并查集简单实现
#pragma once#include vector//可以设计成模板加入哈希表来存放更多的映射关系class UnionFindSet
{
public:UnionFindSet(int size):_set(size, -1){}~UnionFindSet(){}size_t FindRoot(int x){int root x;while (_set[root] 0)root _set[root]; // 向上找到根while (_set[x] 0) // 向上遍历依次修改父亲的父亲结点使其变为根结点的儿子。// 路径压缩{int parent _set[x];_set[x] root;x parent;}return root;}void Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);if (abs(_set[root1]) abs(_set[root2])) // 小优化每次合并都合并到结点更多的树中可以减少层数std::swap(_set[root1], _set[root2]);if (root1 ! root2) // 如果相等说明在一个集合内没必要合并{_set[root1] _set[root2];_set[root2] root1; // 这里默认合并到root1}}int SetCount() // 找根结点个数{size_t count 0;for (size_t i 0; i _set.size(); i){if (_set[i] 0)count;}return count;}
private:std::vectorint _set;
};void TestUFS()
{UnionFindSet u(10);u.Union(0, 6);u.Union(7, 6);u.Union(7, 8);u.Union(1, 4);u.Union(4, 9);u.Union(2, 3);u.Union(2, 5);std::cout u.SetCount() std::endl;
}另外说下压缩路径的问题当并查集的数据非常大时我们要找到这个元素的根可能就需要向上找很久有一种解决方案就是在每次查找的时候如果它的父亲结点不是根结点的话就将它放到根结点的儿子结点。这样就能减少遍历的次数。
并查集虽然是一种数据结构但是有时候又可以是一种解决问题的思路。 比如这道题可以直接手搓一个简单的并查集很容易就秒掉。
class Solution {
public:int findCircleNum(vectorvectorint isConnected) {int n isConnected.size();vectorint set(n,-1);auto findRoot [set](int x){while(set[x] 0)x set[x];return x;};for(int i 0; i n; i){for(int j 0; j n; j){if(isConnected[i][j] 1){int root1 findRoot(i);int root2 findRoot(j);if(root1 ! root2){set[root1] set[root2];set[root2] root1;}}}}int count 0;for(auto x : set){if(x 0)count;}return count;}
}; 总结并查集的特点
1.一个位置的值是负数那么它就是树的根这个负数的绝对值就是这个树结点的个数。
2.一个位置的值是正数那么这个正数就是它父亲结点的下标。
