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
2022-01-28 13:57:13
Took help from two of my friends k[spoiler] and r[spoiler] to solve this

Last edit: 2022-09-02 06:32:06
2022-01-17 16:52:48
stay strong stay [spoiler]

Last edit: 2022-09-02 06:31:45
2021-07-14 16:59:02
Not sure why they mark things as spoiler on problems like this. Who could get the idea wouldn't look at the comments anyway and who couldn't get the idea should learn the name of the algorithm that helps them solve problems like this, [spoiler]

Reply by cegprakash: Because I believe SPOJ isn't like other judges where problems tell you what algorithm to use to solve a problem. Instead I believe it makes us try own algorithm, make mistakes, try different approaches and then google about it, search in forums and then try a different algorithm and get multiple WA/TLE and after a month getting the green light which gives more knowledge than you would have gotten if u solved it quicker. I also believe it's the fun way to learn.

Last edit: 2023-09-08 16:49:23
2019-08-19 19:11:16
I wonder if all of [spoiler], [spoiler]. and [spoiler] will get converted to [spoiler]s automatically.

Last edit: 2019-09-30 14:36:14
2018-01-16 16:03:29
simple [spoiler]

Last edit: 2018-08-22 16:19:58
2017-11-01 13:25:34 Simes
@gohanssj9: from reading the comments, it looks like you need to use the [spoiler] algorithm. (@cegprakash, I self-censored to save you the trouble!)

Reply by author : Thank you!

Last edit: 2018-08-22 16:20:41
2016-09-20 20:33:04 gohanssj9
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.
2016-06-28 15:15:43 Vipul Srivastava
I am constantly getting WA, I have checked multiple test cases. @cegprakash can you please help?

Last edit: 2016-06-28 15:15:56
2016-06-20 15:22:38
[spoiler question] ?

Last edit: 2016-07-29 22:30:42
2016-01-29 01:15:08
the question shouts to implement the [spoiler] algorithm.

Last edit: 2016-07-29 22:31:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.