fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. int n, m;
  6. vector<vector<pair<int, int>>> g;
  7. vector<int> dist, par;
  8. vector<bool> visited;
  9. stack<int> topo;
  10.  
  11. void dfs(int u) {
  12.     visited[u] = true;
  13.     for (auto [v, w] : g[u]) {
  14.         if (!visited[v]) dfs(v);
  15.     }
  16.     topo.push(u);
  17. }
  18.  
  19. int32_t main() {
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(NULL);
  22.  
  23.     cin >> n >> m;
  24.     g.resize(n + 1);
  25.     dist.assign(n + 1, LLONG_MIN);
  26.     par.assign(n + 1, -1);
  27.     visited.assign(n + 1, false);
  28.  
  29.     for (int i = 0; i < m; ++i) {
  30.         int u, v;
  31.         cin >> u >> v;
  32.         g[u].push_back({v, 1}); // longest path -> weight = +1
  33.     }
  34.  
  35.     // Topological sort
  36.     for (int i = 1; i <= n; ++i) {
  37.         if (!visited[i]) dfs(i);
  38.     }
  39.  
  40.     dist[1] = 0;
  41.     while (!topo.empty()) {
  42.         int u = topo.top();
  43.         topo.pop();
  44.         if (dist[u] == LLONG_MIN) continue;
  45.  
  46.         for (auto [v, w] : g[u]) {
  47.             if (dist[v] < dist[u] + w) {
  48.                 dist[v] = dist[u] + w;
  49.                 par[v] = u;
  50.             }
  51.         }
  52.     }
  53.  
  54.     if (dist[n] == LLONG_MIN) {
  55.         cout << "IMPOSSIBLE\n";
  56.         return 0;
  57.     }
  58.  
  59.     cout << dist[n] + 1 << "\n";
  60.     vector<int> path;
  61.     for (int v = n; v != -1; v = par[v]) {
  62.         path.push_back(v);
  63.     }
  64.     reverse(path.begin(), path.end());
  65.     for (int x : path) cout << x << " ";
  66. }
  67.  
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/2Bz8MZ
language:
C++14 (gcc 8.3)
created:
2 days 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!