【数据结构】：由小米的一道面试题入手并查集

小米的面试题

1、题目： 假如已知有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个朋友圈。2、怎么解决？拿到这道题有什么思路？别着急，我们可以用学过的数据结构来进行分析这道题。 首先我们很容易想到哈希，利用哈希桶来进行做这道题，那么如何实施用vector进行存储人，如果有几个人，我们就存储几个，但是当有交集，也就是说当是好友关系的时候，放进桶里，最终统计vector里面的个数针对这道题就是：首先是1,那么放进vector,再是2因为2是1的好友，就放进桶里，接着进行遍历数组，遍历到3,3是2的好友，就将3链接到2的后面，当遇到4的时候，放进vector中，到5，接到4的下面，最终统计出vector里面的数，就是2，因此有两个朋友圈。3、这种方法可解但是我们仔细想想，时间复杂度是很高的，实现起来也是很麻烦的，因此我们想想有没有一种新的方法可以降低时间复杂度，很好的进行实现的，于是就出现了一种新的数据结构：并查集。

并查集

1、定义： 主要用于处理求不相交集合的合并问题。2、利用并查集如何解决小米的面试题： 3、代码实现： #include<iostream> #include<vector> using namespace std; class UnionFindSet { public: //构造函数 UnionFindSet(size_t n) { _ufs.resize(n,-1); } //查找当前数的根 int FindRoot(int x) { while(_ufs[x] > 0) { x = _ufs[x]; } return x; } //合并并查集 void Union(int x1,int x2) { //首先得到两个数的根（因为进行合并的时候是根的合并） int root1 = FindRoot(x1); int root2 = FindRoot(x2); //进行合并，将其中一个根对应的数据加到另一个上， //接着此根的数据变为另一个根 if(root1 != root2) { _ufs[root1] += _ufs[root2]; _ufs[root2] = root1; } } //求有多少个根 int CountRoot() { int count = 0; for(int i = 0; i<_ufs.size(); i++) { if(_ufs[i] < 0) { count++; } } return count; } private: vector<int> _ufs; }; int Friends(int n,int m,int r[][2]) { UnionFindSet u(n+1); //多申请一个空间 for(int i = 0; i<m; i++) { u.Union(r[i][0],r[i][1]); } return u.CountRoot()-1; //这块要减1 } //测试函数 void TestUnionFindSet() { int n = 5; //共有n个人 int m = 3; //有m对好友关系 int r[][2]= {{1,2},{2,3},{4,5}}; //朋友圈 cout<<Friends(n,m,r)<<endl; } 4、并查集小结： 关注点： 每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。应用： 连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等等。