## TFRIENDS - True Friends

no tags

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}

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb   push_back
#define EPS 1e-9
#define FOR(i,n)  for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b)   si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
#define FILL(arr, val)  memset(arr, val, sizeof(arr))
#define read(arr, n)    for(int i = 0;i < n; i++)cin>>arr[i];
#define sp ' '

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

const int MAXN = 1e2+5;
int components[MAXN];   //components[i] indicates to which component i belongs to.
int in_degree[MAXN];
int n;
bool vis[MAXN];
stack<int> stk;
int numberOfComponents;

void initialize(){
}

void dfs(int src){
vis[src] = 1;
}
}
//ordering the vertices according to the finish times, the vertex finishing last will be at the top of stack.
stk.push(src);
}

void dfsF(int src){
vis[src] = 1;
components[src] = numberOfComponents;
}
}
}

void scc(){
while(!stk.empty()){
int ele = stk.top();
stk.pop();
if(!vis[ele]){
numberOfComponents++;
dfsF(ele);
}
}
}

int main(){
io;
int t;
cin >> t;
while(t--){
cin >> n;
initialize();
char matrix[n+1][n+1];
FORE(i,1, n){
FORE(j,1, n){
cin >> matrix[i][j];
}
}
FORE(i,1, n){
FORE(j,1, n){
if(matrix[i][j] == 'Y'){
}
}
}
for(int i = 1;i <= n; i++){
if(!vis[i]){
dfs(i);
}
}
FORE(i,1,n) vis[i] = false;
scc();
cout << numberOfComponents << endl;
//DAG of SCC is formed calculate indegree of components
}
return 0;
}``````
Copy The Code &

Input

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

Output

cmd
1
7
3