Friend circle

Friend Circles – Hacker Earth – BankBazaar Online Coding Test

QUESTION DESCRIPTION

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also 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(char[][] friends) which returns the number of friend circles in the class. Its argument, friends, is a NxN matrix which consists of characters ‘Y’ or ‘N’. If friends[i][j] = ‘Y’, then i and j students are friends with each other, otherwise not. You have to return the total number of friend circles in the class.

Note: The method signature will differ by language. For example, Java will have ‘int friendCircles(String[] friends)’ where “friends” is an array of strings, which can be viewed as a 2-dimensional array of characters.

Constraints
1 <= N <= 300.
Each element of matrix friends will be ‘Y’ or ‘N’.
Number of rows and columns will be equal in friends.
friends[i][i] = ‘Y’, where 0 <= i < N.
friends[i][j] = friends[j][i], where 0 <= i < j < N.

Sample Input #1
4
YYNN
YYYN
NYYN
NNNY

Sample Output #1:
2

Explanation #1:
There are two pairs of friends (0, 1) and (1, 2). So (0, 2) is also a pair of friends by transitivity. So first friend circle contains (0, 1, 2), and second friend circle contains only student 3.

Sample Input #2
5
YNNNN
NYNNN
NNYNN
NNNYN
NNNNY

Sample Output #2:
5

Explanation #2:
No student is friends with any other, so each friend circle will contain of only one student
{0}, {1}, {2}, {3}, {4}.


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
 
/**
 * Created by bipin
 */
public class FriendCircles {
 
    static LinkedList<Integer> queue = new LinkedList<Integer>();
 
    static int friendCircles(String[] friends) {
        String[] tempFriendArray = friends.clone();
        int friendCircleCount=0;
        for (int j=0;j<tempFriendArray.length;j++){
            if (tempFriendArray[j].contains("Y") ){
                friendCircleCount++;
                tempFriendArray[j] = processRow(tempFriendArray[j]);
                while (!queue.isEmpty()){
                    int head = queue.poll();
                    tempFriendArray[head] = processRow(tempFriendArray[head]);
                }
            }
        }
        return  friendCircleCount;
    }
 
    static String processRow(String row){
        Integer indexOfY;
        while((indexOfY=row.indexOf('Y')) != -1){
            queue.addLast(indexOfY);
            row = row.replaceFirst("Y","N");
        }
        return row;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numFriends = Integer.parseInt(scanner.nextLine());
        String[] friends = new String[numFriends];
        for (int i = 0; i < numFriends; i++) {
            friends[i]=scanner.nextLine();
        }
        System.out.println(friendCircles(friends));
    }
}