There are n students in a class. Every student can have 0 or more friends. If A is a friend of B and B is a friend of C then A and C are also friends. So we define a friend circle as a group of students who are friends as given by above definition. Given an nXn-matrix friends which consists of characters Y or N. If friends[i][j]=Y, then ith and jth students are friends, friends[i][j]=N, then i and j are not friends. Find the total number of such friend circles in the class.

Please try solving this problem before jumping on the solution

Click to learn

Subscribe for more updates

Algorithm/Insights

1. We start with the first student (first row), i = 0. set visited[i] = Y 2. Initialize noOfCircles = 1 3. Move to next student j, for which M[i][j] == Y, set visited[j] = Y. 4. Recursively, find friends of j and mark them visited too till all students that can be reached from i=0 are covered. These will form 1 friend circle. 5. Once all friends of student 1 are traversed, we move to next unvisited student and increase noOfCircles by 1. 6. Repeat the above steps till all the students are visited. 7. Return noOfCircles.

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.

Thanks, -Team IDeserve

Algorithm Visualization

Code Snippet

package com.ideserve.saurabh.questions;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* <br><br>
* Friend Circles Graph Problem:</b><br>
* There are n students in a class.
* Every student can have 0 or more friends.
* If A is a friend of B and B is a friend of C then A and C are also friends.
* So we define a friend circle as a group of students who are friends as given by above definition. <br>
* Given an nXn-matrix friends which consists of characters Y or N.
* If friends[i][j]=Y, then ith and jth students are friends, friends[i][j]=N, then i and j are not friends.
* Find the total number of such friend circles in the class.
* <br><br>
* <a href="https://www.youtube.com/watch?v=1XuCGYE56T0">Friend Circle Problem Youtube Link</a>
* @author Saurabh
*
*/
public class FriendCirclesGraph {
public static void main(String[] args) {
char[][] friends = {"YYNN".toCharArray(), "YYYN".toCharArray(), "NYYN".toCharArray(), "NNNY".toCharArray()};
System.out.println(getFriendCircles(friends));
}
public static int getFriendCircles(char[][] friends) {
if (friends == null || friends.length < 1)
return 0;
int noOfCircles = 0;
boolean visited[] = new boolean[friends.length];
for (int i = 0; i < visited.length; i++)
visited[i] = false;
for (int i = 0; i < friends.length; i++) {
if (!visited[i]) {
noOfCircles++;
visited[i] = true;
findFriends(friends, visited, i);
}
}
return noOfCircles;
}
public static void findFriends(char[][] friends, boolean[] visited, int id) {
for (int i = 0; i < friends.length; i++) {
if (!visited[i] && i != id && 'Y' == friends[id][i]) {
visited[i] = true;
findFriends(friends, visited, i);
}
}
}
}

Order of the Algorithm

Time Complexity is O(n^2) Space Complexity is O(n)

Contribution

Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

Saurabh Kumar

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.