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
Thanks
0 comments:
Post a Comment