Cod sursa(job #2705485)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 12 februarie 2021 17:21:41
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 1e5;
const int MMAX = 5e5;
struct {
    int from, to;
} v[MMAX + 1];
vector < int > graf[NMAX + 1];
bool f[MMAX + 1];
vector < int > rez;
void euler ( int node ) {
    while ( graf[node].size() > 0 ) {
        int edge = graf[node].back();
        graf[node].pop_back();
        if ( f[edge] == 0 ) {
            f[edge] = 1;
            euler ( v[edge].from == node ? v[edge].to: v[edge].from );
        }
    }
    rez.push_back ( node );
}
ifstream fin ( "ciclueuler.in" );
ofstream fout ( "ciclueuler.out" );
int main () {
    int n, m;
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        fin >> v[i].from >> v[i].to;
        graf[v[i].from].push_back ( i );
        graf[v[i].to].push_back ( i );
    }
    int i = 1;
    while ( i <= n && graf[i].size() % 2 == 0 )
        i++;
    if ( i < n + 1 )
        fout << -1 << '\n';
    else {
        euler ( 1 );
        rez.pop_back();
        for ( auto x : rez )
            fout << x << ' ';
    }
    
    
    return 0;
}