fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define all(x) x.begin(), x.end()
  6. typedef long long ll;
  7.  
  8. #define inf 1e18
  9. #define vint vector<int>h
  10. #define vll vector<ll>
  11. #define no cout << "NO" << endl;
  12.  
  13.  
  14. void solve() {
  15.     ll n , m ; cin >> n >> m ;
  16.     vector < bool > vis(n+1, false) ;
  17.     vector < set <ll  > > adj(n+1) ;
  18.     vector < ll > dis(n+1)   , pred(n+1, -1);
  19.     for (int i = 0 ; i  < m ; i ++ ) {
  20.         ll a , b ; cin >> a >> b ;
  21.         adj[a].insert(b) ;
  22.         adj[b].insert(a);
  23.     }
  24.     queue < ll > q;
  25.     q.push(1 );
  26.     vis[1] = 1 ;
  27.     dis[1] = 0 ;
  28.     pred[1] = -1 ;
  29.     while (!q.empty()) {
  30.         ll last = q.front() ;
  31.         q.pop() ;
  32.         set < ll > st = adj[last];
  33.         for (auto e : st) {
  34.             if (vis[e]) continue  ;
  35.             vis[e] = 1 ;
  36.             q.push(e) ;dis[e] = dis[last] + 1 ;
  37.             pred[e] = last ;
  38.         }
  39.     }
  40.     ll ans = 0 ;
  41.     string s = to_string(n) ;
  42.     ll last =  n  ;
  43.     ans++;
  44.     while (pred[last] != -1 ) {
  45.         last  =  pred[last ];
  46.         ans++ ;
  47.         s=' '+to_string(last)+s ;
  48.     }
  49.     reverse(s.begin() , s.end()) ;
  50.     cout << ans << endl << s<< endl;
  51.  
  52. }
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59. int main() {
  60.     ios::sync_with_stdio(false);
  61.     cin.tie(nullptr);
  62.  
  63. #ifndef ONLINE_JUDGE
  64.     freopen("input.txt", "r", stdin);
  65.     freopen("output.txt", "w", stdout);
  66. #endif
  67.  
  68.  
  69.     int t = 1 ;
  70.     // cin >> t;
  71.     while (t--) {
  72.         solve();
  73.     }
  74.  
  75. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
0
https://ideone.com/WaJqyE
language:
C++ (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!