Union-Find Solution for Determining Friend Circles (Alibaba Interview Question)

In an Alibaba interview, candidates are asked to solve a problem where friendships are transitive – "a friend of a friend is also a friend" – and to determine how many distinct friend circles exist among a given set of people.

The task consists of two parts: (1) given any two individuals, decide whether they belong to the same friend circle; (2) compute the total number of different friend circles based on the provided friendship pairs.

To model this efficiently, the article introduces the disjoint‑set (union‑find) data structure. Each person is initially its own leader; when a friendship pair is processed, the two leaders are united, merging their circles. Checking whether two people are in the same circle reduces to comparing their leaders.

The algorithm proceeds by initializing all leaders, iterating over the list of friendship pairs to unite sets, then answering query pairs by finding and comparing leaders, and finally counting the remaining distinct leaders to obtain the number of circles.

Below is the complete C++ implementation that follows the described approach:

#include <iostream>
#include <map>
using namespace std;

map<string, string> leader;

// each line represents a pair of friends
string input[] = {
  "周芷若", "张无忌",
  "张无忌", "韩小昭",
  "成昆", "陈友谅",
  "杨逍", "纪晓芙",
};

// test pairs
string test[] = {
  "周芷若", "韩小昭",
  "张无忌", "成昆",
};

void setLeader() {
  int i = 1;
  int totalPerson = 8;
  for(i = 0; i < totalPerson; i++) {
    leader[input[i]] = input[i]; // initialize each as its own leader
  }
}

string findLeader(string s) {
  string r = s;
  while(leader[r] != r) {
    r = leader[r]; // keep climbing up
  }
  return r;
}

void uniteSet(string leaderX, string leaderY) {
  leader[leaderX] = leaderY;
}

int main() {
  int numberOfSets = 7; // initially 7 distinct people
  setLeader();
  int i = 0;
  int j = 0;
  int n = 4; // 4 pairs of relationships
  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 test pairs
  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;
}

The program prints "YES" for the first query (周芷若 and 韩小昭 are in the same circle), "NO" for the second (张无忌 and 成昆 are not), and finally outputs the number of distinct friend circles, which is 3 for the given data.

This example demonstrates how the union‑find structure efficiently solves connectivity queries and counting components, a common topic in coding interviews and algorithm contests.