Trusted answers to developer questions

Educative Answers Team

There are *N* students in a class. Some of them are friends,others are not. Their friendship is transitive; if A is a *direct* friend of B, and B is a *direct* friend of C, then A is an *indirect* friend of C. A friend circle is defined as a group of students who are *direct* or *indirect* friends.

The input matrix will have a number of rows and columns equal to the number of students in a class. A cell `[i,j]`

will hold the value **1** if student `i`

and student `j`

are friends; otherwise, the cell will hold the value **0**. For example, if the input is:

Then there are **2** friend circles. Student **0** is friends with student **1** *only*, but student 1 is friends with *both* student **0** and student **2**. These three students make one friend circle. Student **3**, alone, makes another friend circle.

Similarly, if the input matrix is:

Then there are three friend circles.
Student **0** and student **1** are only friends with each other, so they make one friend circle. Student **2** and student **3** don’t have any friends, so they each make one friend circle.

Let’s try to solve this for *any* value of **n**.

Note that the input matrix will always be

symmetricbecause the friendship is transitive.

We can try to think of the symmetric input matrix as an *undirected* graph. Let’s make an undirected graph for our first example:

Notice that all friends (both direct and indirect), who should be in one friend circle are also in one *connected component* in the graph.

The

number of connected components in the graphwill give us the number of friend circles in the class.

We can treat our input matrix as an **adjacency matrix**; our task is to find the number of connected components. Here are the steps:

- Initialize a list/array,
`visited`

, to keep track of visited vertices of size**n**with**0**as the initial value at each index. - For every vertex
`v`

, if`visited[v]`

is 0, traverse the graph using`DFS`

; else, move to the next`v`

. - Set
`visited[v]`

to**1**for every`v`

that the DFS traversal encounters. - When the
`DFS`

traversal terminates, increment the friend circles counter by**1**as it means that one whole connected component has been traversed.

The following code snippet implements the above algorithm:

#include <iostream> #include <vector> using namespace std; //Recursively finds all students in a single friend circle void DFS(vector< vector<bool> >friends, int n, vector<bool> &visited, int v) { 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[v][i] == 1 && !visited[i] && i != v) { visited[i] = 1; DFS(friends, n, visited, i); } } } int friendCircles(vector< vector<bool> >friends, int n) { if (!n) { return 0; } int numCircles = 0; //Number of friend circles //Keep track of whether a student is already in a friend circle vector<bool> visited (n, 0); //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 (!visited[i]) { visited[i] = true; DFS(friends, n, visited, i); //Recursive step to find all friends numCircles++; } } return numCircles; } int main() { int n = 4; bool friends_temp[n][n] = { {1,1,0,0}, {1,1,1,0}, {0,1,1,0}, {0,0,0,1} }; vector< vector<bool> > friends; for (int i=0; i < n; i++) { vector<bool> temp; for (int j=0;j < n;j++) temp.push_back(friends_temp[i][j]); friends.push_back(temp); } cout << "Number of friends circles: " << friendCircles(friends, n); return 0; }

RELATED TAGS

Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring

Related Courses