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”
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?
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
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.
We can solve it using Djikstra too.By making edge weights negative(-1).
Yes we can solve it this way too.
I don’t think Longest Path problem can be solved using Dijkstra’s algorithm, because one characteristic of Dijkstra’s algorithm is that whenever a node is selected, its distance is final.
Consider this in a Shortest Path Problem, we choose a node such that the distance to it from source is minimum among all, thus any other node cannot improve its distance. So its distance is final.
However, In Longest Path Problem, if you choose a node with maximum distance from source, this distance may not be final. Its possible that some other node (currently with lesser distance) extend and increase the answer for chosen node.
Thus a Greedy Algorithm like Dijkstra shouldn’t work in Longest Path Problem. So if not Greedy, may be Dynamic Programming? Yeah, this problem can be solved using DP. Many problems involving a acyclic directed graph can be solved by DP. Only thing to keep in mind is to decide the order in which the dp states should be computed. This can be done by finding the Topological sorting for DAG. As Topological sort resembles DFS a lot, you can even skip topological sort and implement a DFS version.
I am getting TLE only on test case 17. Then I submitted your code, it is also getting TLE. I think cses has updated test cases for this problem.
Longest path is NP-Hard by a reduction from Hamiltonian Path Problem,
You can solve this by simply sorting in topological order and then dp.
Solved using Applying only Topological Sort two times. 1st time - without considering node 1 . Second time - considering Node 1.
Link: https://cses.fi/paste/9ee3d2f988dc939e6047e1/
No Dijkstra cannot be applied for negative weight