fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define maxm 1000005
  7. #define maxn 100005
  8. ll par[maxn], dau[maxn];
  9. vector<ll> edges[maxm];
  10. vector<ll> res;
  11. ll s, n, m, t;
  12. void solve(ll destination)
  13. {
  14.     // dbg(destination);
  15.     if (destination == par[destination])
  16.     {
  17.         res.push_back(destination);
  18.         return;
  19.     }
  20.     res.push_back(destination);
  21.     destination = par[destination];
  22.     solve(destination);
  23. }
  24. void dfs(ll source)
  25. {
  26.     stack<ll> st;
  27.     st.push(source);
  28.     while(!st.empty()){
  29.         ll p = st.top();
  30.         dau[p]=1;
  31.         if(p==t){
  32.             solve(t);
  33.             return ;
  34.         }
  35.         st.pop();
  36.         for(auto v: edges[p]){
  37.             if(dau[v]==1) continue;
  38.             par[v]=p;
  39.             st.push(v);
  40.             // break;
  41.         }
  42.     }
  43. }
  44.  
  45. int main()
  46. {
  47.     freopen("input.txt", "r", stdin);
  48.     freopen("output.txt", "w", stdout);
  49.     cin >> n >> m >> s >> t;
  50.     s--, t--;
  51.     for (ll i = 0; i < m; i++)
  52.     {
  53.         ll u, v;
  54.         cin >> u >> v;
  55.         u--, v--;
  56.         edges[u].push_back(v);
  57.     }
  58.     for (ll i = 0; i < n; i++)
  59.         sort(edges[i].begin(), edges[i].end(),greater<ll>());
  60.     // for(ll i=0;i<n;i++){
  61.     //     cout<<i+1<<"-->";
  62.     //     for(auto q: edges[i]) cout<<q+1<<" ";
  63.     //     cout<<'\n';
  64.     // }
  65.     par[s] = s;
  66.     dfs(s);
  67.     // cout<<1;
  68.     reverse(res.begin(), res.end());
  69.     for (auto v : res)
  70.         cout << v + 1 << " ";
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 28032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0V34LJ
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!