Cod sursa(job #3237877)

Utilizator tsg38Tsg Tsg tsg38 Data 13 iulie 2024 22:05:37
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

const int MAXN = 1e5 + 1;
const int MAXM = 5e5 + 1;

vector<pair<int, int>> G[MAXN];
bool off[MAXM], viz[MAXN];

int dfs( int u ) {
  int sz = 1;
  viz[u] = true;
  for ( auto [v, i] : G[u] ) {
	if ( !viz[v] ) {
	  sz += dfs(v);
	}
  }
  return sz;
}

vector<int> cyc;

void build_cycle( int u ) {
  for ( auto [v, i] : G[u] ) {
	if ( !off[i] ) {
	  off[i] = true;
	  build_cycle(v);
	}
  }
  cyc.push_back(u);
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, m, u, v;

  fin >> n >> m;
  for ( int i = 1; i <= m; ++i ) {
	fin >> u >> v;
	G[u].push_back({v, i});
	G[v].push_back({u, i});
  }
  bool ok = true;
  for ( int i = 1; i <= n; ++i ) ok &= (G[i].size() % 2 == 0);
  ok &= (dfs(1) == n);
  if ( !ok ) {
	fout << "-1\n";
  } else {
	build_cycle(1);
	cyc.pop_back();
    for ( auto u : cyc ) fout << u << " ";
  }
  fin.close();
  fout.close();
  return 0;
}