fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Macros
  5. #define pb          push_back
  6. #define pf          push_front
  7. #define ff          first
  8. #define ss          second
  9. #define all(v)      v.begin(), v.end()
  10. #define rall(v)     v.rbegin(), v.rend()
  11.  
  12. #define rep(i, x, n)   for(int i = x; i < n; ++i)
  13. #define rrep(i, x, n)  for(int i = x; i >= n; --i)
  14.  
  15. // Read and Print
  16. #define read(a, i, n) for(ll i = 0; i < n; ++i) cin >> a[i];
  17. #define print(a, i, n) for(ll i = 0; i < n; ++i){ cout << a[i] << " ";} cout << "\n";
  18.  
  19. // Typedefs
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair <ll, ll> pii;
  23.  
  24. typedef vector <ll> vi;
  25. typedef vector <vector <ll>> vvi;
  26.  
  27. // Constants
  28. const ll mxn = 1e5 + 5;
  29. const ll mod = 1e9 + 7;
  30.  
  31. // Fast IO
  32. void fast(){
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(0); cout.tie(0);
  35. }
  36.  
  37. // Solve
  38.  
  39. vector <set <int>> adj(mxn);
  40. vector <int> in(mxn), out(mxn);
  41. vector <int> path;
  42.  
  43. void dfs(int root){
  44. 	while(adj[root].size()){
  45. 		int m = adj[root].size();
  46. 		int it = *adj[root].begin();
  47.  
  48. 		adj[root].erase(it);
  49. 		adj[it].erase(root);
  50. 		dfs(it);
  51. 	}
  52.  
  53. 	path.pb(root);
  54. }
  55.  
  56. void solve() {
  57.  
  58.     int n, m;
  59.     cin >> n >> m;
  60.  
  61.     for(int i = 0; i < m; ++i){
  62.     	int u, v;
  63.     	cin >> u >> v;
  64.     	--u, --v;
  65.  
  66.     	adj[u].insert(v);
  67.     	adj[v].insert(u);
  68.  
  69.     	in[u]++, in[v]++, out[u]++, out[v]++;
  70.     }
  71.  
  72.     // print(in, i, n);
  73.     // print(out, i, n);
  74.  
  75.     bool ok = 1;
  76.  
  77.     for(int i = 0; i < n; ++i){
  78.     	if(in[i] != out[i]){
  79.     		ok = 0; break;
  80.     	}
  81.     	if(in[i] % 2 == 1){
  82.     		ok = 0; break;
  83.     	}
  84.     }
  85.  
  86.     if(!ok) cout << "IMPOSSIBLE\n";
  87.     else{
  88.     	dfs(0);
  89.  
  90.     	// print(path, i, path.size());
  91.  
  92.     	if(path.size() == m + 1){
  93.     		reverse(path.begin(), path.end());
  94.     		rep(i, 0, path.size()){
  95.     			cout << path[i] + 1 << " ";
  96.     		}
  97.     		cout << "\n";
  98.     	}
  99.     	else{
  100.     		cout << "IMPOSSIBLE\n";
  101.     	}
  102.     }
  103. }
  104.  
  105. int main(){
  106.  
  107.     // fast();
  108.     solve();
  109.  
  110.     return 0;
  111. }
Runtime error #stdin #stdout 0.04s 8768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FBA8MQ
language:
C++14 (gcc 8.3)
created:
178 days ago
visibility:
secret

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!