Cod sursa(job #3289307)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 26 martie 2025 15:01:35
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

#define cin fin
#define cout fout


#define PB push_back
#define F first
#define S second

const int Nmax = 1e5 + 1;

typedef pair<int, int> pii;

int deg[Nmax];
vector<int> cycle;
multiset<int> adj[Nmax];
stack<int> st;

int main()
{
    int n, m, i, u, v, nod_crt, nod_next;
    bool exista;

    cin >> n >> m;
    for( i = 0; i < m; i ++ ) {
      cin >> u >> v;

      adj[u].insert( v );
      adj[v].insert( u );

      deg[u]++;
      deg[v]++;
    }

    exista = true;
    for( i = 1; i < n + 1; i ++ )
      if( deg[i] % 2 != 0 )
        exista = false;

    if( !exista )
      cout << -1 << '\n';
    else {
      st.push( 1 );
      while( !st.empty() ) {
        nod_crt = st.top();
        if( adj[nod_crt].empty() ) {
          st.pop();
          cycle.PB( nod_crt );
        } else {
          int nod_next = *adj[nod_crt].begin();
          st.push( nod_next );

          adj[nod_crt].erase( adj[nod_crt].begin() );
          auto it = adj[nod_next].find( nod_crt );
          adj[nod_next].erase( it );
        }
      }
    }

    for( i = 0; i < cycle.size() - 1; i++ )
      cout << cycle[i] << ' ';
    return 0;
}