fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int const maxN = 205;
  4. int n, m, in[maxN];
  5. bool visited[maxN];
  6. set <pair <int, int>> adj[maxN];
  7. void inp(){
  8.   cin >> n >> m;
  9.   for(int i=1; i<=m; i++){
  10.     int u, v, w; cin >> u >> v >> w;
  11.     adj[u].insert({v, w});
  12.     adj[v].insert({u, w});
  13.   }
  14. }
  15. // 1 0
  16. // 2 2
  17. // 3 -1
  18. // 1 -1
  19.  
  20. void dfs(int u){
  21.   visited[u] = true;
  22.   for(auto it : adj[u]){
  23.    int v = it.first;
  24.     if(!visited[v]) dfs(v);
  25.   }
  26. }
  27. void Count_In(){
  28.   for(int i=1; i<=n; i++){
  29.     in[i] += adj[i].size();
  30.   }
  31. }
  32. bool check(){
  33.   for(int x=1; x<=n; x++){
  34.     if(in[x]!=0){
  35.       dfs(x); break;
  36.     } //bug7
  37.   }
  38.   for(int i=1; i<=n; i++){
  39.     if(!visited[i] && in[i] != 0) return false;// bug4
  40.     if(in[i] % 2 != 0) return false;
  41.   }
  42.   return true;
  43. }
  44. bool Euler_Cycle(int s, set <pair <int, int>> adj[maxN]){
  45.   if(in[s]==0) return false;//bug6
  46.   stack <pair <int, int>> st;
  47.   vector <pair <int, int>> EC;
  48.   st.push({s, 0});//bug1
  49.   int sum = 0;
  50.   // for(int i=1; i<=n; i++){
  51.   //   cout << i << " : ";
  52.   //   for(auto it : adj[i]){
  53.   //     cout << "(" << it.first << " " << it.second << ")" << " ";
  54.   //   }
  55.   //   cout << endl;
  56.   // }
  57.   while(!st.empty()){
  58.     auto it = st.top();
  59.     auto [u, w] = it;
  60.     if(adj[u].size()){
  61.       auto it2 = *adj[u].begin();
  62.       auto [v, w2] = it2;
  63.  
  64.       st.push(it2);
  65.       adj[u].erase(it2);
  66.       adj[v].erase({u, w2});//bug3
  67.     }
  68.     else{
  69.       st.pop();
  70.       EC.push_back(it);
  71.     }
  72.   }
  73.  
  74.   reverse(EC.begin(), EC.end());
  75.   for(auto it : EC) {
  76.     auto [x, w] = it;
  77.     sum += w;
  78.     if(sum < 0) return false;
  79.   }
  80.   for(int i=0; i<=m; i++){
  81.     cout << EC[i].first;
  82.     if(i != EC.size()-1) cout << " ";
  83.   }
  84.   cout << endl;
  85.   return true;
  86. }
  87. int main() 
  88. {
  89.     ios_base::sync_with_stdio(false);
  90.     cin.tie(0); cout.tie(0); 
  91.     inp();
  92.     Count_In();
  93.     if(check()){
  94.       set <pair <int, int>> adj_fake[maxN];//bug2-5
  95.       for(int i=1; i<=n; i++){
  96.         for(int j=1; j<=n; j++) adj_fake[j] = adj[j];//bug2
  97.         if(Euler_Cycle(i, adj_fake)) return 0;
  98.       }
  99.     }
  100.     cout << -1 << endl;
  101.     return 0;
  102. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/RLhBB5
language:
C++14 (gcc 8.3)
created:
146 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!