Friend Circles Problem - Graph Theory

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.

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)