Friday, June 26, 2015

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×Nmatrix 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
1N300
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 0i<N
M[i][j] = M[j][i], where 0i<j<N

Here is the code

Thanks