Submit | All submissions | Best solutions | Back to list |
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: ASM32-GCC MAWK BC BF C NCSHARP C++ 4.3.2 CPP14 COBOL COFFEE D-CLANG D DART ELIXIR FANTOM FORTH GOSU GRV JULIA KTLN LUA NODEJS OBJC OCAML OCT PIKE PROLOG PYPY3 PYTHON3 R RACKET RUST CHICKEN ST SQLITE SWIFT UNLAMBDA |
hide comments
2014-03-30 13:25:39 cegprakash
durga: just draw and play! You can easily generate test cases for this problem! |
|
2014-03-30 11:47:55 durga
more test cases please |
|
2014-03-29 14:24:29 vivek n
@pavitrakumar thats why output is 7 consider each of individual as a true friend e.g. group1{0}, group2{1},group3{2}……. at least thats what i think…. Last edit: 2014-03-29 14:24:57 |
|
2014-03-29 14:22:50 xZiOn
case 2: no 2 true friends exist, but the o/p is 7?.. Last edit: 2014-03-29 14:23:03 |