Cod sursa(job #3215997)

Utilizator dorufDoru Floare doruf Data 15 martie 2024 15:37:54
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define eb emplace_back

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int N = 1e5 + 5;
vector<pair<int,int>> g[N];
int n, m;
vi ans;
bool vis[5*N];

void dfs(int u) {
  while (!g[u].empty()) {
    int v = g[u].back().first;
    int i = g[u].back().second;
    g[u].pop_back();
    if (!vis[i]) {
      vis[i] = 1;
      dfs(v);
    }
  }
  ans.eb(u);
}

int main() {
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);

  fin >> n >> m;
  for (int u, v, i = 1; i <= m; ++i) {
    fin >> u >> v;
    g[u].eb(v,i); g[v].eb(u,i);
  }
  for (int i = 1; i <= n; ++i) {
    if (g[i].size()%2) {
      fout << "-1\n";
      return 0;
    }
  }
  dfs(1);
  for (auto i : ans)
    fout << i << ' ';
}