Disjoint Set

Disjoint Set，最基本的操作就是 Union 和 Find 两个函数。

Union 有根据size和rank两种方法，而 Find 通常使用 path compression 来提升后续搜索的效率。

时间复杂度等可以参考 http://web.eecs.utk.edu/~plank/plank/classes/cs302/Notes/Disjoint/

 

实现一：建立parent数组，这样做实现起来非常简单，但是也只适用于集合元素是从0开始自然数（比如一个数组下标）。

Union 根据size合并。

#include <iostream>class DisjointSet{ public:DisjointSet(int size):parent(size,-1){}void Union(int x, int y){int root1=Find(x), root2=Find(y);if (root1==root2) return;// whoever's size is bigger becomes parent of other// notice parent[root] is negative, if parent[root] is smaller, then its size is largerif (parent[root1]>parent[root2]){parent[root2] += parent[root1];parent[root1] = root2;}else{parent[root1] += parent[root2];parent[root2] = root1;}}int Find(int x){if (parent[x]<0) return x;return parent[x] = Find(parent[x]);}private:vector<int> parent; };int main() {DisjointSet s(10);s.Union(2,1);cout << s.Find(1);return 0; }

 

实现二：创建一个结构体Node，成员是val和指向parent的指针。相比上一种方法的好处是，val没有限制。同时需要一个hashmap将val的值映射到Node *，用来找Node。

Union 根据rank合并。

#include <iostream>struct Node{int val;Node *parent;int rank;Node(int v):val(v),parent(this),rank(0){} };class DisjointSet{ public:// Create a set with only one elementvoid makeSet(int val){Node *node=new Node(val);m[val] = node;}// Combines two sets, unions by rankvoid unionSet(int val1, int val2){Node *node1=m[val1];Node *node2=m[val2];Node *root1=findSet(node1);Node *root2=findSet(node2);// they of part of the same set, do nothingif (root1==root2) return;// whoever's rank is higher becomes parent of otherif (root1->rank > root2->rank)root2->parent = root1;else if (root1->rank < root2->rank)root1->parent = root2->parent;else{root1->rank += 1;root2->parent = root1;}}int findSet(int val){return findSet(m[val])->val;}// Find the representative recursively and does path compression as wellNode *findSet(Node *node){Node *parent=node->parent;if (parent==node) return node;node->parent = findSet(node->parent);return node->parent;}private:unordered_map<int,Node *> m; // node val -> Node * };int main(){DisjointSet a;for (int i=1;i<=7;++i) a.makeSet(i);a.unionSet(1,2);a.unionSet(2,3);cout << a.findSet(1) << endl;cout << a.findSet(3) << endl;cout << a.findSet(7) << endl;return 0; }

 

应用中，可以简化Union，不用根据size，rank合并，直接把一个节点的root赋为另一个节点root的父亲即可。

 

转载于:https://www.cnblogs.com/hankunyan/p/9998626.html

总结

以上是生活随笔为你收集整理的Disjoint Set的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。