从零开始网站建设下载,上海搬家公司收费,绍兴网站seo,网站建设全网营销客户资源0. 引入
并查集是来解决等价问题的数据结构。
离散数学中的二元关系。
等价关系需满足自反性、对称性、传递性。 a ∈ S , a R a a R b b R a a R b ∩ b R c a R c a \in S, aRa \\ aRb \ bRa \\ aRb \cap bRc aRc a∈S,aRaaRbbRaaRb∩bRca…0. 引入
并查集是来解决等价问题的数据结构。
离散数学中的二元关系。
等价关系需满足自反性、对称性、传递性。 a ∈ S , a R a a R b b R a a R b ∩ b R c a R c a \in S, aRa \\ aRb \ bRa \\ aRb \cap bRc aRc a∈S,aRaaRbbRaaRb∩bRcaRc
1. 需要实现的操作
给定n个数据看能划分多少个等价类。
初始时即分为n个等价类然后再一一合并。
所以需要实现的操作为
合并两个等价类查找元素属于哪个等价类
2. 实现
2.0 父节点
vectorint pa;2.1 查找
int Find(int k)
{return k pa[k] ? k : Find(pa[k]);
}2.2 合并
void Union(int a0, int a1)
{int p0 Find(a0);int p1 Find(a1);if ( p0 ! p1 ) {pa[p0] p1;}
}2.3 路径压缩
对于查找来说如果简单的递归的话最坏的情况便是全都在左子树。
如(0,1) (0,2) (0,3) (0, 4) ... (0, n) 这样会导致单次查询如同一个链表一样达到O(n)。
只需要改动一点点就可以完成路径压缩。
int Find(int k)
{
return k pa[k] ? k : pa[k] Find(pa[k]);
}2.4 按节点数合并
可以令开一个数组记录当前节点下的节点数。在合并的时候取小的节点合并到大的节点上去。
void Union(int a1, int a2)
{int p1 Find(a1);int p2 Find(a2);if ( p1 p2)return;if (sz[p1] sz[p2]) {pa[p1] p2;sz[p2] sz[p1];}else {pa[p2] p1;sz[p1] sz[p2];}
}3. 类封装
3.1 路径压缩
class UnionFind {public:explicit UnionFind(int sz):cnt(sz),pa(sz){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k pa[k] ? k : pa[k] Find(pa[k]);}void Union(int k1, int k2 ){int p0 Find(k1);int p1 Find(k2);if ( p0 ! p1) {pa[p0] p1;cnt--;}}int Cnt(){return cnt;}private:vectorint pa;int cnt;
};3.2 按节点数合并
public:
class UnionFind {public:explicit UnionFind(int _sz):cnt(_sz),pa(_sz),sz(_sz, 1){iota(pa.begin(), pa.end(), 0);}int Find(int k ){return k pa[k] ? k : Find(pa[k]);}void Union(int k1, int k2 ){int p0 Find(k1);int p1 Find(k2);if (p0 p1)return ;if (sz[p0] sz[p1] ) {pa[p0] p1;sz[p1] sz[p0];}else {pa[p1] p0;sz[p0] sz[p1];}}int Cnt(){return cnt;}int Size(int idx){ return sz[idx]; }private:vectorint pa,sz;int cnt;
};
4. 参考
lFoll题解 OIWIKI
