本文共 2005 字，大约阅读时间需要 6 分钟。
并查集是用于将n个不同元素分成一组不相交集合的数据结构
带路径压缩和按秩合并的并查集
在实现上，数组中的每一个值的绝对值代表当前集合的元素个数 两个操作的时间复杂度几乎为常数class ufs{ private: int* father; public: ufs(int size) { father = new int[size]; for(int i = 0;i < size;i++)//这里的设计很精妙 father[i] = -1; //用正数会带来混乱，数组绝对值为该集合个数 } int find(int w) { if(father[w] < 0) //找到根 return w; return father[w] = find(father[w]); //路径压缩 //迭代实现 /*while(father[w] >= 0) { father[w] = father[father[w]]; w = father[w]; } return w;*/ } void _union(int w,int v) { int fw = find(w); int fv = find(v); if(fw == fv)//属于同一个集合 return ; //按秩合并 //这里看绝对值 if(father[fw] > father[fv])//集合fw的个数小于fv { father[fv] += father[fw];//小的加到大的上面 father[fw] = fv; } else { father[fw] += father[fv]; father[fv] = fw; } }}; 下面给出以展现并查集这个非常精妙的数据结构
这道题，是很典型的并查集，寻找不相交集合的个数。在上面ufs的基础上增加一个变量成员num，用于记录当前不相交集合的个数。每合并一次少一个。实际上我们只遍历了1/2(n2-n)个元素class ufs{ private: int* father; public: int num; ufs(int size) { num = size; father = new int[size]; for(int i = 0;i < size;i++) father[i] = -1; //用正数会带来混乱，数组绝对值为该集合个数 } int find(int w) { if(father[w] < 0) //找到根 return w; return father[w] = find(father[w]); //路径压缩 } void _union(int w,int v) { int fw = find(w); int fv = find(v); if(fw == fv)//属于同一个集合 return ; //按秩合并 //这里看绝对值 if(father[fw] > father[fv])//集合fw的个数小于fv { father[fv] += father[fw];//小的加到大的上面 father[fw] = fv; } else { father[fw] += father[fv]; father[fv] = fw; } num--; return; }};class Solution { public: int findCircleNum(vector >& M) { ufs s(M.size()); for(int i = 0;i < M.size();i++) //这里我们只需要遍历下三角 for(int j = 0;j <= i;j++) if(M[i][j] && i!=j) s._union(i,j); return s.num; }};int main(){ Solution s; vector > M = { { 1,0,0,1},{ 0,1,1,0},{ 0,1,1,1},{ 1,0,1,1}}; cout< 转载地址：http://qxhrn.baihongyu.com/