fork(4) 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.     dau[source] = 1;
  27.     if (source == t)
  28.     {
  29.         solve(t);
  30.         return;
  31.     }
  32.     for (auto v : edges[source])
  33.     {
  34.         if (dau[v] == 0)
  35.         {
  36.             par[v] = source;
  37.             dfs(v);
  38.         }
  39.     }
  40. }
  41.  
  42. int main()
  43. {
  44.     freopen("input.txt", "r", stdin);
  45.     freopen("output.txt", "w", stdout);
  46.     cin >> n >> m >> s >> t;
  47.     s--, t--;
  48.     for (ll i = 0; i < m; i++)
  49.     {
  50.         ll u, v;
  51.         cin >> u >> v;
  52.         u--, v--;
  53.         edges[u].push_back(v);
  54.     }
  55.     for (ll i = 0; i < n; i++)
  56.         sort(edges[i].begin(), edges[i].end());
  57.     // for(ll i=0;i<n;i++){
  58.     //     // cout<<i+1<<"-->";
  59.     //     for(auto q: edges[i]) cout<<q+1<<" ";
  60.     //     cout<<'\n';
  61.     // }
  62.     par[s] = s;
  63.     dfs(s);
  64.     // cout<<1;
  65.     reverse(res.begin(), res.end());
  66.     for (auto v : res)
  67.         cout << v + 1 << " ";
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 27620KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gtG2Aj
language:
C++14 (gcc 8.3)
created:
2 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!