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

help
, , ,
1

Question : “CSES - Longest Flight Route”

My solution -

lli dist[MAX];
lli parent[MAX];
int vis[MAX];
vi adj[MAX];

void dfs(lli src , lli lvl)
{
    vis[src]=1;
    dist[src] = lvl;
    
    for(auto xt : adj[src])
    {
        if(!vis[xt])
        {
            parent[xt] = src;
            dfs(xt , lvl+1);
        }
        else
        {
            if(dist[xt] < dist[src]+1)
            {
                dist[xt] = dist[src]+1;
                parent[xt] = src;
            }
        }
    }
}

int main(){
fastio
lli t=1;
//cin>>t;
chandan2();
while(t--) {
    
    lli n,m;
    
    cin>>n>>m;
    
    loop(i,m)
    {
        lli x,y;
        cin>>x>>y;
        adj[x].pb(y);
    }
    dfs(1,0);
    
    if(dist[n]==0)
        print("IMPOSSIBLE");
    else
    {
        vi ans;
        ans.pb(n);
        while(n!=1)
        {
            n = parent[n];
            ans.pb(n);
        }
        
        reverse(all(ans));
        print(sz(ans));
        printvec(ans);
    }
  }
return 0;
}

I just did dfs and if already visited node occurs then change its parent if and only if the current distance is more , it shows WA in 3 TC’s and they are very big .

@galencolin @aryan12 @everule1 @ssjgz @aneee004

1 Like
2

What all macros are you using? I am not too familiar with them so need them for reference.

3

“o7J7IL - Online C++0x Compiler & Debugging Tool - Ideone.com”

4

Another case of people using global vis and adj and not clearing them between testcases :sob:

1 Like
5

Nope , only single test case in question.

2 Likes
6

Oh yeah - lli t=1; XD

1 Like
7

So please review my code and tell me where i m doing mistake . I also take max as 200050

8

Whats your answer for following test case
6 7
1 2
2 3
3 4
4 5
5 6
4 6
1 5

PS - answer should be
6
1 2 3 4 5 6

9

same answer .

10

If your answer is not matching than this test case should be enough to put you on right track.
I have not yet tested your code because of unavailability of your template .

11

Sorry my fault
6 7
1 5
5 6
1 2
2 3
3 4
4 5
4 6

Try on this

12

Just saw your ideone code and tested on this case. Answer is coming out to be wrong for this case
6 7
1 5
5 6
1 2
2 3
3 4
4 5
4 6

1 Like
13

what should be correct answer ?

14

got it , thanks .

1 Like
15

this is the correct answer
6
1 2 3 4 5 6

1 Like
16

But I can’t figure out what should I change , for the above test case my answer is correct after sorting the adjacency list before dfs call , but my approach is wrong.

17

topological sort

19

How?

20

All right first of all lets talk whats wrong in your approach and how to correct it.

What your are doing wrong is that if a dist of a node comes out to be larger than what we calculated previously than you are simply updating the distance of that node and not updating the distance of all of its child nodes. Now this might seem right from time complexity point of view but the test that I gave you proves this wrong.

So obviously if a distance of node (for simplicity lets call this node A) is changed you need to perform dfs on node A again such that we also update the distance of its child nodes. But this approach will give TLE as time complexity in worst case might go to O(m^2).

You can improve time complexity in this case by using a method known as dfs in out time to keep track of child nodes of a particular node and than using segment tree to update all of its child nodes.

But I think topological sort is an easier alternative.But why?
Simple - Lets say that I have a sequence of node and if I reach a particular node A than then that sequence ensures that distance of node A up to that point is maximum from root node. If i go further in the sequence after crossing A,then distance of A from root node will not change.
In this way I just need to update the distance of child nodes of A once. That is right when we reach A.
Also there will be no need to do a full dfs on node A just updating the distance of its child nodes should be fine as in our sequence we will reach its child nodes at some point and also reach child of its child node at some point and at some point reach the final node.

So hopefully you got idea about what I am talking about upto this point.

How to get that sequence?
Turns out that topological sort gives us exactly that sequence just because of the fact that every node which might the parent of A are already been taken care of as they all are at left of our node.

3 Likes
22

can u please share code , So that I understand in better way , I did topo sort and i have list of nodes in topo order , but after that I find difficulty to understand.