Friend Circles Problem - Graph Theory

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



Preparing for interviews? IDeserve team is here to help.




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.


Hone your coding skills!




AngryNerds Practice platform »

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

    Ninja Programmer