Friend Circles Programming Problem - C++ Solution

Home / Friend Circles Programming Problem - C++ Solution

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". )

Leave a Reply

Your email address will not be published. Required fields are marked *