CSES Longest Flight Route Solution 1680 | 𝓣𝓸𝓹𝓸𝓵𝓸𝓰𝓲𝓬𝓪𝓵 Sort

CSES Longest Flight Route Solution

Link to the Question :  CSES Longest Flight Route Solution

https://cses.fi/problemset/task/1680/

Answer : CSES 1680 Longest Flight Route

Input

The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n1,2,…,. City 11 is Syrjälä, and city n is Lehmälä.

After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. Each flight is a one-way flight.

Output

First print the maximum number of cities on the route. After this, print the cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print “IMPOSSIBLE”.

Constraints

• 2≤n≤10⁵
• 1≤m≤2⋅10⁵
• 1≤a,b≤n

Example

Input:
5 5
1 2
2 5
1 3
3 4
4 5

Output:
4
1 3 4 5

 

Hint 1 :  Using Topological Sort.

Hint 2 :  Use Topological Sort Two Times.

Explanation :

Do Topological Sorting without considering Node 1 , you have to consider every other  node except the Node 1 . Now , Node 1 and all other nodes between source and destination is left . So now you perform the Topological Sort Again , this time consider Node 1 , to get the Answer.

Solution for CSES Longest Flight Route Solution in C++:

 

#include<bits/stdc++.h>
using namespace std;
 
#define ll                  long long int
#define mod                 1000000007
#define inf                 1e9
#define endl                "\n"
#define pb                  push_back
#define vi                  vector
#define ff                  first
#define ss                  second
#define loop(i,a,b)         for(int i=a ; i<=b ; i++)
     


const int N =1e6;
vector<int> Adj(N,vector());
vector<int> Par(N,-1);
vector<int> Deg(N,0);
 
void topo(queue< int > &Q;)
{
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
 
        for(ll t : Adj[x])
        {
            Deg[t]--;
            if(Deg[t] == 0)
            {   
                Par[t] = x;
                if(t != 1)
                {
                    Q.push(t);
                }
                
            }
        }
    }
}
 
int main(int argc, char const *argv[])
{
    /* code */
    
    ll n,m;
    cin>>n>>m;
    ll a,b;
    for(ll i= 1; i<=n ; i++)
    {
        Deg[i] = 0;
        Par[i] =-1;
    }
    loop(i,0,m-1)
    {
        cin>>a>>b;
        Adj[a].pb(b);
        Deg[b]++;
    }
 
 
 
    queue< int > Q;
    for(ll i= 2; i<=n;i++)
    {
        if(Deg[i] == 0)
        {
            Q.push(i);
        }
    }
    topo(Q);
    Q.push(1);
    Par[n] = -1;
    Par[1] = -1;
    topo(Q);
 
    if(Par[n] == -1)
    {
        cout<<"IMPOSSIBLE";
    }
   else
    {
        ll cur = n;
        vector Ans;
        while(Par[cur] != -1)
        {
            Ans.push_back(cur);
            cur = Par[cur];
        }
        Ans.push_back(1);
        cout<<Ans.size()<<endl;
        reverse(Ans.begin(),Ans.end());
        loop(i,0,Ans.size()-1)
        {
            cout<<Ans[i]<<" ";
        }
    }
 
    return 0;
}

Thank You !