fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long int
  5. #define vi vector<int>
  6. #define vvi vector<vi>
  7. #define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
  8. #define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
  9. #define pb push_back
  10. #define pql priority_queue<int>
  11. #define pqs priority_queue<int, vi, greater<int>>
  12. #define pqlv priority_queue<vi>
  13. #define pqsv priority_queue<vi, vvi, greater<vi>>
  14. #define endl '\n'
  15. #define N 1234567
  16. #define MOD 1000000007
  17.  
  18. vvi adj;
  19. vi par, vis;
  20. int n, mx;
  21.  
  22. bool dfs(int u, int d = 0) {
  23.     if(u == n) {
  24.         if(d > mx) {
  25.             mx = d;
  26.             return true;
  27.         }
  28.         return false;
  29.     }
  30.     if(vis[u])
  31.         return false;
  32.     vis[u] = 1;
  33.     bool ans = false;
  34.     for(int v : adj[u]) {
  35.         if(dfs(v, d + 1)) {
  36.             par[v] = u;
  37.             ans = true;
  38.         }
  39.     }
  40.     return ans;
  41. }
  42.  
  43. signed main() {
  44.     ios::sync_with_stdio(false); 
  45.     cin.tie(0); 
  46.     cout.tie(0);
  47.     int t = 1;
  48.     // cin >> t;
  49.     while(t--) {
  50.         int m;
  51.         cin >> n >> m;
  52.         adj.clear();
  53.         adj.resize(n + 1);
  54.         mx = 0;
  55.         par.assign(n + 1, -1);
  56.         vis.assign(n + 1, 0);
  57.         for(int i = 0; i < m; i++) {
  58.             int a, b;
  59.             cin >> a >> b;
  60.             adj[a].pb(b);
  61.         }
  62.         if(dfs(1, 0)) {
  63.             int v = n;
  64.             cout << mx + 1 << endl;
  65.             vi ret;
  66.             while(v != 1) {
  67.                 ret.pb(v);
  68.                 v = par[v];
  69.             }
  70.             ret.pb(1);
  71.             reverse(ret.begin(), ret.end());
  72.             for(int i : ret)    cout << i << " ";
  73.         }
  74.         else {
  75.             cout << "IMPOSSIBLE";
  76.         }
  77.         cout << endl;
  78.     }
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin
copy 
5 5
1 2
2 5
1 3
3 4
4 5
stdout
copy 
4
1 3 4 5
https://ideone.com/U6kCsI
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!