fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int oo = 1e9 + 7;
  5. const int N = 1e5 + 7;
  6.  
  7. int n,m,s,t;
  8. bool vis[N];
  9. int par[N];
  10. vector<int>v[N], ans;
  11.  
  12. void bfs(int s){
  13.     queue<int>q;
  14.     q.push(s);
  15.  
  16.     vis[s] = 1;
  17.  
  18.     while(!q.empty()){
  19.         int u = q.front();
  20.         q.pop();
  21.  
  22.         for(auto x : v[u]){
  23.             if(!vis[x]){
  24.                 vis[x] = 1;
  25.                 par[x] = u;
  26.                 q.push(x);
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32. signed main(){
  33.     ios_base::sync_with_stdio(0); cin.tie(0);
  34.  
  35.     cin >> n >> m >> s >> t;
  36.  
  37.     for(int i=1; i <= m; i++){
  38.         int a,b; cin >> a >> b;
  39.         v[a].push_back(b);
  40.         v[b].push_back(a);
  41.     }
  42.  
  43.     bfs(s);
  44.  
  45.     if(!vis[t]) cout << -1;
  46.  
  47.     else{
  48.         int cur = t;
  49.         while(cur != -1){
  50.             ans.push_back(cur);
  51.             if(cur == s) break;
  52.             cur = par[cur];
  53.         }
  54.  
  55.         reverse(ans.begin(), ans.end());
  56.  
  57.         cout << ans.size() << "\n";
  58.         for(auto x : ans) cout << x << " ";
  59.     }
  60. }
  61.  
Success #stdin #stdout 0.01s 5920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
0
https://ideone.com/MUUHyQ
language:
C++14 (gcc 8.3)
created:
4 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!