# Help needed , CSES Longest Flight Route , [Graph Problem 11]

Ok here is the code that you need to do after topsort

``````for(auto x:topsort){
for(auto y:graph[x]){
if(lvl[x] + 1 > lvl[y]){
lvl[y] = lvl[x] + 1;
last[y] = x;
}
}
}
``````

here lvl keeps track of the distance from root the particular node and last keeps track of previous number of array

I don’t know but using topological sorting still my code give WA on four Test cases
Que : “CSES - Longest Flight Route

help @carre @cubercoder @samarth2017
also if we apply dijkistra as this code (“QsHX3c - Online C++0x Compiler & Debugging Tool - Ideone.com”) gives TLE on last test cases so i apply Topo sort , but why WA ?

try this testcase

4 3
1 4
2 3
3 4

``````#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
bool vis[100001];
lli child[100001];
lli cnt[100001];
bool flag[100001];
vector<lli> v[100001];
lli dfs(lli node)
{
vis[node]=true;
for(lli chil:v[node])
{
//cout<<chil<<" ";
if(!vis[chil])
{
dfs(chil);
}
flag[node]|=flag[chil];
if((cnt[node]<cnt[chil]+1)&&(flag[chil]==true))
{
cnt[node]=cnt[chil]+1;
child[node]=chil;
}
}
//if(node==5) return 1;
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli T;
T=1;
while(T--)
{
lli n,m,i;
cin>>n>>m;
lli x,y;
for(i=0;i<m;i++)
{
cin>>x>>y;
v[x].pb(y);
}
flag[n]=true;
x=dfs(1);
/*for(i=1;i<=n;i++)
cout<<child[i]<<" ";*/
if(!flag[1])
{
cout<<"IMPOSSIBLE\n";continue;
}
cout<<cnt[1]+1<<"\n";
cout<<"1 ";
lli z=1;
while(child[z]!=n)
{
cout<<child[z]<<" ";
z=child[z];
}
cout<<n;
}
return 0;
}
``````

Tell me if you are unable to understant. It is An AC code.

Did you understood the solution or should I explain?

can you share the full code ? @anon59051972

@dhruv788 would you please explain why you used flag[]

It stores that whether we can reach the current node from n

https://cses.fi/paste/3719bdc61c805cb029b40b/

This is my solution and I think I am using same approach, hope it helps
( Ignore macros, I am not using any of them here)

Here’s a slightly different aproach, since the given graph is a DAG