阿里面试：周芷若和韩小昭的并查集

点击关注公众号，一周多次包邮送书

来源：经授权转自 爱码有道（ID：aimayoudao）作者：道哥在阿里巴巴的文化中，充满了各种武侠元素。在面试阿里时，也经常会出现一些有趣的题目，今天，我们来看一道阿里巴巴面试的题目：在武林中，朋友的朋友还是朋友，比如朋友关系如下表所示，那么周芷若、张无忌、韩小昭属于一个朋友圈，成昆和陈友谅属于一个朋友圈，杨逍和纪晓芙属于一个朋友圈。最终，不同朋友圈的个数是3.

人物	人物	关系
周芷若	张无忌	朋友
张无忌	韩小昭	朋友
成昆	陈友谅	朋友
杨逍	纪晓芙	朋友

(1)任意给定两个人，判断他们是否属于同一个朋友圈。
(2)编程求出不同朋友圈的个数。

题目理解

首先，我们来看看周芷若、张无忌和韩小昭长什么样子吧，还是挺可爱的。张无忌这家伙，笑得挺开心，别问为什么，懂的自然懂。

我来解释什么叫“朋友的朋友还是朋友”：周芷若和张无忌是朋友，张无忌和韩小昭是朋友。所以，他们三人是朋友，属于同一个朋友圈。趣味动图解释如下：

思路分析

在解决这个问题之前，我们得想一种合理的数据结构，然而，貌似书本上的数据结构都不合适，那怎么办呢？

我们来讲一个周芷若与并查集的故事。先来分析一下，好友关系如下：

 {周芷若，张无忌} {张无忌，韩小昭} {成昆，陈友谅} {杨逍，纪晓芙}
他们关系的逻辑图如下：

从上图可知，这些人属于不同的3个朋友圈，那么这3个朋友圈是怎么得出来的呢？

很显然，我们可以在每个朋友圈定义一个名义上的leader. 

• 如果要判断两个人是否属于一个朋友圈，只需要判断他们的leader是否为同一个人，这是一个查询的过程。
  

• 如果两个人是好友关系，则需要把两个人并入同一个朋友圈，这是一个合并的过程。

这一查一并的操作，就分出了最终有多少个朋友圈，对应的数据结构就是并查集。在很多笔试面试或ACM竞赛中，并查集屡见不鲜。

编程实现

根据上述思路分析，我们用C++代码来实现并查集，并给出测试和结果。代码的注释非常详细，所以不再赘述：

#include <iostream>#include <map>using namespace std;
map<string, string> leader;
// 每一行表示一对朋友关系string input[] = { "周芷若", "张无忌", "张无忌", "韩小昭", "成昆", "陈友谅", "杨逍", "纪晓芙",};
// 测试每行的两个人是否为朋友string test[] ={ "周芷若", "韩小昭", "张无忌", "成昆",};
// 初始化void setLeader(){ int i = 1; int totalPerson = 8; for(i = 0; i < totalPerson; i++) { leader[input[i]] = input[i]; // 将自己初始化为自己的领导 }}
// 查找领导，看看究竟是谁string findLeader(string s) { string r = s; while(leader[r] != r) { r = leader[r]; // 没找到的话，一直往上找 }
return r;}
// 将两个领导的朋友圈合并, 从此，leaderX和leaderY是一个朋友圈了void uniteSet(string leaderX, string leaderY){ leader[leaderX] = leaderY; }
int main(){ int numberOfSets = 7; // 最开始有7个不重复的人
// 初始化领导 setLeader();
int i = 0; int j = 0; int n = 4; // 人物关系的数组有4行 for(j = 0; j < n; j++) { string u = input[i++]; string v = input[i++];
// 找领导 u = findLeader(u); v = findLeader(v);
// 领导不相等，则合并两个朋友圈 if(u != v) { uniteSet(u, v); numberOfSets--; } }
i = 0; n = 2; // 待测试人物关系的数组有2行 for(j = 0; j < n; j++) { string u = test[i++]; string v = test[i++];
// 找领导 u = findLeader(u); v = findLeader(v);
// 如果领导不相同，则不属于一个朋友圈； if(u != v) { cout << "NO" << endl; } else // 如果两个领导相同，则肯定属于一个朋友圈 { cout << "YES" << endl; } } cout << numberOfSets << endl;
return 0;}

程序结果为：

YESNO3很显然，周芷若和韩小昭是朋友关系，张无忌和成昆不是朋友关系，而且，朋友圈个数为3,  如上程序可以通过阿里的面试。希望大家对并查集了如指掌，顺利通过笔试、面试，拿到更好的offer.并查集很有意思，也是经常涉及到的考点，关键还是在于思路。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。最后，来看一段舞蹈吧，皆大欢喜。你好，我是道哥，CSDN前30名，曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。·················END·················

推荐阅读

👇更多内容请点击👇