乱婬妺妺躁爽A片,学生妹一级片,黄色的学生妹一级片,国产偷拍第一页,丰满人妻一区二区三区免费,毛片美女视频,久久国产乱子伦精品免费女,网站,AV操逼网,91天天综合网,天天综合网

在阿里巴巴的文化中，充滿了各種武俠元素。在面試阿里時，也經(jīng)常會出現(xiàn)一些有趣的題目。

今天，我們來看一道阿里巴巴面試的題目：

在武林中，朋友的朋友還是朋友，比如朋友關(guān)系如下表所示，那么周芷若、張無忌、韓小昭屬于一個朋友圈，成昆和陳友諒屬于一個朋友圈，楊逍和紀(jì)曉芙屬于一個朋友圈。最終，不同朋友圈的個數(shù)是 3。

人物	人物	關(guān)系
周芷若	張無忌	朋友
張無忌	韓小昭	朋友
成昆	陳友諒	朋友
楊逍	紀(jì)曉芙	朋友

(1)任意給定兩個人，判斷他們是否屬于同一個朋友圈。

(2)編程求出不同朋友圈的個數(shù)。

題目理解

首先，我們來看看周芷若、張無忌和韓小昭長什么樣子吧，還是挺可愛的。

我來解釋什么叫“朋友的朋友還是朋友”：周芷若和張無忌是朋友，張無忌和韓小昭是朋友。所以，他們?nèi)耸桥笥?，屬于同一個朋友圈。趣味動圖解釋如下：

思路分析

在解決這個問題之前，我們得想一種合理的數(shù)據(jù)結(jié)構(gòu)，然而，貌似書本上的數(shù)據(jù)結(jié)構(gòu)都不合適，那怎么辦呢？

我們來講一個周芷若與并查集的故事。先來分析一下，好友關(guān)系如下：

?{周芷若，張無忌}

?{張無忌，韓小昭}

?{成昆，陳友諒}

?{楊逍，紀(jì)曉芙}

他們關(guān)系的邏輯圖如下：

從上圖可知，這些人屬于不同的 3 個朋友圈，那么這 3 個朋友圈是怎么得出來的呢？

很顯然，我們可以在每個朋友圈定義一個名義上的 leader。?

如果要判斷兩個人是否屬于一個朋友圈，只需要判斷他們的 leader 是否為同一個人，這是一個查詢的過程。
如果兩個人是好友關(guān)系，則需要把兩個人并入同一個朋友圈，這是一個合并的過程。

這一查一并的操作，就分出了最終有多少個朋友圈，對應(yīng)的數(shù)據(jù)結(jié)構(gòu)就是并查集。在很多筆試面試或 ACM 競賽中，并查集屢見不鮮。

編程實現(xiàn)

根據(jù)上述思路分析，我們用 C++ 代碼來實現(xiàn)并查集，并給出測試和結(jié)果。代碼的注釋非常詳細(xì)，所以不再贅述：

#include #include using namespace std;
map<string, string> leader; 
// 每一行表示一對朋友關(guān)系string input[] = {  "周芷若", "張無忌",  "張無忌", "韓小昭",  "成昆", "陳友諒",   "楊逍", "紀(jì)曉芙",};
// 測試每行的兩個人是否為朋友string test[] ={  "周芷若", "韓小昭",  "張無忌", "成昆",};
// 初始化void setLeader(){  int i = 1;  int totalPerson = 8;  for(i = 0; i < totalPerson; i++)  {    leader[input[i]] = input[i]; // 將自己初始化為自己的領(lǐng)導(dǎo)  }}
// 查找領(lǐng)導(dǎo)，看看究竟是誰string findLeader(string s) {  string r = s;  while(leader[r] != r)  {    r = leader[r]; // 沒找到的話，一直往上找  }
  return r;}
//?將兩個領(lǐng)導(dǎo)的朋友圈合并，從此，leaderX和leaderY是一個朋友圈了void uniteSet(string leaderX, string leaderY){  leader[leaderX] = leaderY; }
int main(){  int numberOfSets = 7; // 最開始有7個不重復(fù)的人
  // 初始化領(lǐng)導(dǎo)  setLeader();
  int i = 0;  int j = 0;  int n = 4; // 人物關(guān)系的數(shù)組有4行  for(j = 0; j < n; j++)  {    string u = input[i++];    string v = input[i++];
    // 找領(lǐng)導(dǎo)    u = findLeader(u);    v = findLeader(v);
    // 領(lǐng)導(dǎo)不相等，則合并兩個朋友圈    if(u != v)    {      uniteSet(u, v);      numberOfSets--;    }  }
  i = 0;  n = 2; // 待測試人物關(guān)系的數(shù)組有2行  for(j = 0; j < n; j++)  {    string u = test[i++];    string v = test[i++];
    // 找領(lǐng)導(dǎo)    u = findLeader(u);    v = findLeader(v);
????//?如果領(lǐng)導(dǎo)不相同，則不屬于一個朋友圈    if(u != v)    {      cout << "NO" << endl;    }    else // 如果兩個領(lǐng)導(dǎo)相同，則肯定屬于一個朋友圈    {      cout << "YES" << endl;    }  }   cout << numberOfSets << endl;
  return 0;}