TFRIENDS - True Friends

You are given a string array representing Known people. Known[i][j]='Y' if i knows j.

Friends: A is a friend of B if B knows A or B has a friend who knows A.

True friends: A and B are true friends if A is a friend of B and B is a friend of A.

Group: Everyone in a Group must be true friends to each other.

Your task is to find the number of Groups from the given list of Known people. It can be proved that there is exactly only one possible way for forming the groups.

Input: The first line consists of an integer t, the number of test cases. For each test case, you are given an array of strings representing Known people. Known is of size NxN where N is the total number of people.

Output: For each test case, print the number of Groups.

Input Constraints:

1<=t<=1000

1<=N<=100

Known[i][j] is either 'Y' or 'N'

Known[i][i]='N' (Nobody knows themselves)

Sample Input:

3
3
NYN
NNY
YNN
7
NNYNNNN
NNNYYYN
NNNNNNN
YNNNNNN
NNNYNNN
NNNNNNN
NNNNNYN
7
NNNNYYN
NNNNNNN
NNNNNYN
NYNNNYY
NNNYNNN
NNYNNNY
NNNNYNN

 

Sample Output:

1
7
3

 

Explanation:

Case 1: All the friends are true friends to each other

Case 2: No two true friends exist.

Case 3: There are 3 groups of true friends. {0}, {1}, {2,3,4,5,6}


Added by:cegprakash
Date:2014-03-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF

hide comments
2016-01-24 22:14:20 Arjav
[spoiler]....:)

Last edit: 2016-07-29 22:31:17
2015-11-04 11:57:19 varun yadav
Piece of cake,, without seeing any reference

Last edit: 2015-11-04 11:57:52
2015-10-08 12:47:07
Simply find the [spoiler removed]

Last edit: 2015-10-12 14:19:29
2015-09-13 13:51:00
Hi, can anyone tell me the working approach of this question.. how to get tutorial or something
2015-08-05 09:13:39 pk
O(n^3) giving tle


Last edit: 2015-08-05 11:10:26
2015-05-14 11:48:13 Rohan Jain
@cegprakash if A is a friend of B, will that imply B knows A..?
2014-05-23 16:41:18 sathyanarayanan
@cegprakash I know, you are the fan of these kind of problems!
2014-04-17 09:19:08 cegprakash
anurag garg : Is it that hard to write a test case generator and a tester code?
2014-04-09 16:53:43 anurag garg
@author can you have a look at my submission id:11415247 and tell me whats wrong with my algorithm
thanks
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.