➤ Problem Link : 645D. Robot Rapping Results Report
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pp pair<int,int>
#define mp make_pair
vector<int> adj[200001];
int n,m;
int root;
pp edges[100001];
int dp[200001];
int depth(int v)
{
int dpt=1;
for(int i=0;i<adj[v].size();i++)
{
if(dp[adj[v][i]])
dpt=max(dpt,dp[adj[v][i]]+1);
else
dpt=max(dpt,depth(adj[v][i])+1);
}
return dp[v]=dpt;
}
bool func(int m)
{
for(int i=1;i<=n;i++)
{
adj[i].clear();
dp[i]=0;
}
for(int i=0;i<m;i++)
adj[edges[i].first].push_back(edges[i].second);
if(depth(root) == n)
return 1;
return 0;
}
int main()
{
int x,y;
cin>>n>>m;
int in[n+1];
memset(in,0,sizeof(in));
for(int i=0;i<m;i++)
{
cin>>x>>y;
edges[i].first=x;
edges[i].second=y;
in[y]++;
}
root=-1;
for(int i=1;i<=n;i++)
if(in[i]==0)
{
root=i;
break;
}
int low=0,mid,high=m;
while(low<high)
{
mid=low+(high-low)/2;
if(func(mid))
high=mid;
else
low=mid+1;
}
if(func(low))
cout<<low;
else
cout<<"-1";
}
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.