假如已知有n个人和m对好友关系（存于数组r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈。请写程序求出这n个人里一共有多少个朋友圈。

例如：n=5，m=3，r={{1，2}，{2，3}，{4，5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于同一个朋友圈，4、5属于另一个朋友圈。结果为2个朋友圈。


这个问题可以通过数据结构中的并查集来实现。


并查集

将N个不同的元素分成一组不相交的集合。

开始时，每个元素就是一个集合，然后按规律将两个集合合并。


代码如下：

UnionFindSet.h：

#pragmaonceclassUnionFindSet{public:UnionFindSet(intN):_a(newint[N]),_n(N){memset(_a,-1,N*4);//将每一组初始的元素值设为-1}//找该元素的根intFindRoot(intx){while(_a[x]>=0){x=_a[x];}returnx;}//合并voidUnion(intx1,intx2){introot1=FindRoot(x1);introot2=FindRoot(x2);_a[root1]+=_a[root2];//将元素2的根合并到元素1的根上_a[root2]=root1;//元素2的值设置为元素1}//合并后集合总数intCount(){intcount=0;for(size_ti=0;i<_n;++i){if(_a[i]<0){++count;}}returncount;}protected:int*_a;//元素集合size_t_n;//元素个数};

Test.cpp

#include<iostream>usingnamespacestd;#include"UnionFindSet.h"intGroupsOfFriends(intn,intm,intr[][2]){UnionFindSetufs(n+1);for(size_ti=0;i<m;++i){intx1=r[i][0];intx2=r[i][1];ufs.Union(x1,x2);}returnufs.Count()-1;//元素集合从0开始，应减去0的集合}voidTest(){intr[][2]={{1,2},{1,3},{4,5}};intcount=GroupsOfFriends(5,3,r);cout<<count<<endl;}intmain(){Test();return0;}

过程：