Advertisement
stephk005

Untitled

Jun 2nd, 2020
1,550
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <cstring>
  10. #include <utility>
  11. #include <iomanip>
  12.  
  13. #define ll long long
  14. #define pb push_back
  15.  
  16. #define INF 2e9 + 10
  17. #define PI acos(-1.0)
  18. #define LL_INF 4e17
  19. #define EPS 1e-9
  20.  
  21. const int MOD = 1e9 + 7;
  22. const int MAXN = 1e5 + 5;
  23.  
  24. using namespace std;
  25.  
  26. void fileIO(string prob) {
  27.     freopen((prob + ".in").c_str(), "r", stdin);
  28.     freopen((prob + ".out").c_str(), "w", stdout);
  29. }
  30.  
  31. void fastIO() {
  32.     cin.tie(0)->sync_with_stdio(0);
  33. }
  34.  
  35. // ..... glhf ^-^ .....//
  36.  
  37. int n, m;
  38. vector<int> adj[100005];
  39. vector<int> radj[100005];
  40. int len[100005], pre[100005];
  41.  
  42. void dfs(int par, int v, int leng) {
  43.     len[v] = max(len[v], leng);
  44.     pre[v] = par;
  45.  
  46.     for(int u : adj[v]) {
  47.         if(len[v] + 1 > len[u]) dfs(v, u, leng + 1);
  48.     }
  49. }
  50.  
  51. int main() {
  52.     cin>>n>>m;
  53.     while(m--) {
  54.         int a, b; cin>>a>>b;
  55.         adj[a].pb(b);
  56.         radj[b].pb(a);
  57.     }
  58.  
  59.     dfs(-1, 1, 0);
  60.     if(len[n] == 0) {
  61.         cout<<"IMPOSSIBLE";
  62.         return 0;
  63.     }
  64.  
  65.     int nd = n;
  66.  
  67.     vector<int> ans;
  68.  
  69.     for(int i=n ; i != -1 ; i = pre[i]) ans.pb(i);
  70.  
  71.     cout<<ans.size()<<'\n';
  72.     for(int i=ans.size()-1 ; i>=0 ; i--) {
  73.         cout<<ans[i]<<" ";
  74.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement