C++实现并查集

本文实例为大家分享了C实现并查集的具体代码供大家参考具体内容如下12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include iostream#include vector#include cassertusingnamespacestd;classUnionFind{private:vectorint parent;intcount;//优化记录p和q所在组的深度在合并时将深度小的结点的根指向深度大的结点的根vectorint rank;public:UnionFind(intcount){parent.resize(count);rank.resize(count);this-count count;for(inti 0; i count; i){parent[i] i;rank[i] 1;}}~UnionFind(){parent.clear();rank.clear();}//路径压缩intfind(intp){assert(p 0 p count);if(p ! parent[p])parent[p] find(parent[p]);returnparent[p];}boolisConnected(intp,intq){returnfind(p) find(q);}voidunionElement(intp,intq){intpRoot find(p), qRoot find(q);if(pRoot qRoot)return;if(rank[pRoot] rank[qRoot])parent[pRoot] qRoot;elseif(rank[qRoot] rank[pRoot])parent[qRoot] pRoot;else{//两者的rank相等parent[pRoot] qRoot;rank[qRoot] 1;}}};小编再补充一段代码之前收藏的一段代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include iostreamusingnamespacestd;classUF {//cnt is the number of disjoint sets.//id is an array that records distinct identity of each set,when two sets are merged ,their id will be same.//sz is an array that records the child number of each set including the set self.int*id, cnt, *sz;public:// Create an empty union find data structure with N isolated sets.UF(intN) {cnt N;id newint[N];sz newint[N];for(inti 0; iN; i) {id[i] i;sz[i] 1;}}~UF() {delete[] id;delete[] sz;}// Return the id of component corresponding to object p.intfind(intp) {if(p ! id[p]){id[p] find(id[p]);}returnid[p];}// Replace sets containing x and y with their union.voidmerge(intx,inty) {inti find(x);intj find(y);if(i j)return;// make smaller root point to larger oneif(sz[i] sz[j]) {id[i] j;sz[j] sz[i];}else{id[j] i;sz[i] sz[j];}cnt--;}// Are objects x and y in the same set?boolconnected(intx,inty) {returnfind(x) find(y);}// Return the number of disjoint sets.intcount() {returncnt;}};voidmain(){UF test(5);test.merge(2, 3);test.merge(3, 4);cout test.find(4);cout test.count();}同时谢谢这位作者的分享