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

My Code : “657nFB - Online C++ Compiler & Debugging Tool - Ideone.com

image

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 :slight_smile:
( Ignore macros, I am not using any of them here)

Here’s a slightly different aproach, since the given graph is a DAG
https://cses.fi/paste/0f33adb06516d81c29b492/

i found a video on yt on the same question, it was explained there that just making edge weights -1
and applying dijkstra would work. (kindoff single source longest path problem). was it wrong?
Please reply. I mean this problem seems like single source longest path prob … then why are the testcases failing when i apply dijkstra after make weights negative.

Dijkstra can’t solve longest path problem.