➤ Problem Link : TFRIENDS
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
vector<int> adj[100005];
vector<int> adj2[100005];
bool visited[100005];
void dfs(int v, stack<int> &s)
{
for(int i=0;i<adj[v].size();i++)
{
if(!visited[adj[v][i]])
{
visited[adj[v][i]]=1;
dfs(adj[v][i],s);
}
}
s.push(v);
}
void dfs2(int v)
{
for(int i=0;i<adj2[v].size();i++)
{
if(!visited[adj2[v][i]])
{
visited[adj2[v][i]]=1;
dfs2(adj2[v][i]);
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
adj[i].clear();
adj2[i].clear();
visited[i]=0;
}
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<s.length();j++)
{
if(i==j)
continue;
if(s[j]=='Y')
{
adj[i].pb(j);
adj2[j].pb(i);
}
}
}
stack<int> s;
for(int i=0;i<n;i++)
{
if(!visited[i])
{
visited[i]=1;
dfs(i,s);
}
}
for(int i=0;i<n;i++)
visited[i]=0;
int ans=0,v;
while(!s.empty())
{
v=s.top();
s.pop();
if(visited[v])
continue;
ans++;
visited[v]=1;
dfs2(v);
}
cout<<ans<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.