Friend Circle - Hackerrank

Problem Reference - Hackerrank

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/number-of-provinces/.

Problem

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 are given a N×N−matrix M which consists of characters Y or N. If M[i][j]=Y, then ith and jth students are friends with each other, otherwise not. You have to print the total number of friend circles in the class.
Input Format
First line of the input contains an integer N - (size of the matrix), followed by N lines each having N characters.
Output Format
Print the maximum number of friend circles.
Constraints
1≤N≤300
Each element of matrix friends will be Y or N.
Number of rows and columns will be equal in the matrix.
M[i][i]=Y, where 0≤i<N
M[i][j] = M[j][i], where 0≤i<j<N

Here is the code

	package com.vaani.hackerrank;
	import java.util.ArrayList;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;
	/**
	* Created by mdev on 4/8/15.
	*/
	public class FriendsCircle {
	public static void main(String[] args) {
	String[] friends = new String[]{"YYNN", "YYYN", "NYYN", "NNNY"};
	String[] friends1 = new String[]{"YNNNN", "NYNNN", "NNYNN", "NNNYN","NNNNY"};
	int result = friendCircles(friends1);
	System.out.println("result = " + result);
	}
	static int friendCircles(String[] friends) {
	List<Set> list = new ArrayList<>();
	for (int friend = 0; friend < friends.length; friend++) {
	String contacts = friends[friend];
	for (int contact = 0; contact < contacts.length(); contact++) {
	Set<Integer> s1 = null, s2 = null;
	if (contacts.charAt(contact) == 'Y') {
	for (Set s : list) {
	if (s.contains(friend))
	s1 = s;
	if (s.contains(contact))
	s2 = s;
	}
	if (s1 == null && s2 == null) {
	Set<Integer> newSet = new HashSet<>();
	newSet.add(contact);
	newSet.add(friend);
	list.add(newSet);
	} else if (s1 == null && s2 != null) {
	s2.add(friend);
	} else if (s2 == null && s1 != null) {
	s1.add(contact);
	} else {//both not null
	if(s1 != s2) {
	for (Integer s : s2) {
	s1.add(s);
	}
	list.remove(s2);
	}
	}
	}
	}
	}
	System.out.println(list);
	return list.size();
	}
	}

view raw FriendsCircle hosted with ❤ by GitHub

Thanks