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' (No one is known to 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}
hide comments
Simes:
20171101 13:25:34
@gohanssj9: from reading the comments, it looks like you need to use the [spoiler] algorithm. (@cegprakash, I selfcensored to save you the trouble!) Last edit: 20171101 13:29:11 

gohanssj9:
20160920 20:33:04
Hi,can anyone tell me how you people managed to get the execution time under 0.50sec? I mean,which algorithm should we use to get that kind of timing? Thank you. 

Vipul Srivastava:
20160628 15:15:43
I am constantly getting WA, I have checked multiple test cases. @cegprakash can you please help? Last edit: 20160628 15:15:56 

princekumar:
20160620 15:22:38
[spoiler question] ? Last edit: 20160729 22:30:42 

naruto09:
20160129 01:15:08
the question shouts to implement the [spoiler] algorithm. Last edit: 20160729 22:31:04 

Arjav:
20160124 22:14:20
[spoiler]....:) Last edit: 20160729 22:31:17 

varun yadav:
20151104 11:57:19
Piece of cake,, without seeing any reference Last edit: 20151104 11:57:52 

thenamesake:
20151008 12:47:07
Simply find the [spoiler removed] Last edit: 20151012 14:19:29 

nehaa:
20150913 13:51:00
Hi, can anyone tell me the working approach of this question.. how to get tutorial or something 

pk:
20150805 09:13:39
O(n^3) giving tle

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