C++是如何实现并查集的-创新互联
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
创新互联是一家专注于成都做网站、网站制作与策划设计,孙吴网站建设哪家好?创新互联做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:孙吴等地区。孙吴做网站价格咨询:028-86922220小编给大家分享一下C++是如何实现并查集的,希望大家阅读完这篇文章后大所收获,下面让我们一起去探讨吧!
#include#include #include using namespace std; class UnionFind{ private: vector parent; int count; //优化,记录p和q所在组的深度,在合并时将深度小的结点的根指向深度大的结点的根 vector rank; public: UnionFind(int count){ parent.resize(count); rank.resize(count); this->count = count; for(int i = 0; i < count; ++i){ parent[i] = i; rank[i] = 1; } } ~UnionFind(){ parent.clear(); rank.clear(); } //路径压缩 int find(int p){ assert(p >= 0 && p < count); if(p != parent[p]) parent[p] = find(parent[p]); return parent[p]; } bool isConnected(int p, int q){ return find(p) == find(q); } void unionElement(int p, int q){ int pRoot = find(p), qRoot = find(q); if(pRoot == qRoot) return; if(rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot; else if(rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot; else{ //两者的rank相等 parent[pRoot] = qRoot; rank[qRoot] += 1; } } };
网站标题:C++是如何实现并查集的-创新互联
网页链接:http://myzitong.com/article/dhpodh.html