I recently solved an interesting programming challenge, called Friend Circles, and wanted to share my solution, which was implemented in C++.

## Problem statement

There are N students in a class. Some of them are friends, while some of them are not. Their friendship is transitive in nature, i.e., if A is a friend of B and B is a friend of C, then A is also a friend of C. A friend circle is a group of students who are directly or indirectly friends.

You have to complete a function `int friendCircles(vector<std::string> friends)`

which returns the number of friend circles in the class. Its argument, *friends*, is an array of strings. However, for the sake of this problem, *friends* should be viewed as a 2-dimensional array of characters (the input has N strings and each string has N characters). Therefore, *friends* is a NxN matrix which consists of characters 'Y' or 'N'. If *friends[i][j]* = 'Y', then students *i* and *j* are friends which each other, otherwise not. You have to return the total number of friend circles in the class.

### Constraints:

- 1 <= N <= 300
- Each element of matrix
*friends*will be either'Y' or 'N' - Number of row and columns in
*friends*will be equal *friends[i][i]*= 'Y', where 0 <= i < N*friends[i][j] = friends[j][i]*

### Example inputs/return values

#### Example 1

YYNN

YYYN

NYYN

NNNY

should output 2. There are two pairs of friends (0, 1) and (1, 2). So (0, 2) is also a pair of friends by transitivity. So the first friend circle contains (0, 1, 2) and the second friend circle contains only student 3.

#### Example 2

YNNNN

NYNNN

NNYNN

NNNYN

NNNNY

should output 5 because no student is friends with any other. So each student forms its own friend circle, for a total of 5.

## Solution (C++)

Note that, since *friends* is an NxN matrix where *friends[i][j] = friends[j][i]*, the input can be thought of as an undirected graph. Each student represents a node in the graph and there is an edge between two nodes if the corresponding students are friends. If there is a path in the graph from student A to student B, then, by transitivity, students A and B must be in the same friend circle. Therefore, we can use a DFS/BFS to find each student in a friend circle. The general algorithm for this problem can be represented as follows:

1. Create an array to keep track of whether a student has been visited by the DFS/BFS. This can also be thought of to represent whether or not that student has already been placed in a friend circle.

2. Starting with the first student, use a DFS to find each student in the same friend circle. Mark each student as being "visited".

3. Increment the number of friend circles.

4. Repeat steps 2 and 3, starting with the next student that is not already part of a friend circle.

(For those more familiar with graph theory, note that each friend circle would constitute a connected component on the graph. Therefore, this problem can be abstracted out to be the same as "How to find the number of connected components in an undirected graph". )

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//Forward Declaration void findFriendCircle(const vector<string> friends, vector<bool> &inCircle, int studentIndex); /* * Complete the function below. */ int friendCircles(vector < string > friends) { if (friends.empty()) { return 0; } int numCircles = 0; //Number of friend circles int n = friends.size(); //Number of students //Keep track of whether a student is already in a friend circle vector<bool> inCircle (n, false); //Start with the first student and recursively find all other students in his/her //friend circle. Then, do the same thing for the next student that is not already //in a friend circle. Repeat until all students are in a friend circle. for (int i = 0; i < n; ++i) { if (!inCircle[i]) { inCircle[i] = true; findFriendCircle(friends, inCircle, i); //Recursive step to find all friends ++numCircles; } } return numCircles; } //Recursively finds all students in a single friend circle void findFriendCircle(const vector<string> friends, vector<bool> &inCircle, int studentIndex) { int n = friends.size(); for (int i = 0; i < n; ++i) { //A student is in the friend circle if he/she is friends with the student represented by //studentIndex and if he/she is not already in a friend circle if (friends[studentIndex][i] == 'Y' && !inCircle[i] && i != studentIndex) { inCircle[i] = true; findFriendCircle(friends, inCircle, i); } } } |