Cod sursa(job #2565182)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 2 martie 2020 12:40:01
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>

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

const int NMAX = 100000;
const int MMAX = 500000;

struct Node {
    int node;
    int ord;
};

std::vector <Node> edges[1 + NMAX];
int grad[1 + NMAX];
bool viz[1 + MMAX];
int start[1 + NMAX];
std::vector <int> sol;

void euler ( int node ) {
    for ( int i = start[node]; i < edges[node].size(); ++i ) {
        int newNode = edges[node][i].node;
        start[node] = i + 1;
        if ( !viz[edges[node][i].ord] ) {
            viz[edges[node][i].ord] = 1;
            euler ( newNode );
        }
    }
    sol.push_back ( node );
}
        
int main() {
    int N, M;

    fin >> N >> M;
    for ( int i = 1; i <= M; ++i ) {
        int x, y;
        fin >> x >> y;
        edges[x].push_back ( ( Node ) { y, i } );
        edges[y].push_back ( ( Node ) { x, i } );
        ++grad[x];
        ++grad[y];
    }

    bool ok = 1;

    for ( int i = 1; i <= N; ++i )
        if ( grad[i] % 2 == 1 )
            ok = 0;

    if ( ok == 1 ) {
        euler ( 1 );
        for ( int i = 0; i < sol.size() - 1; ++i )
            fout << sol[i] << ' ';
    } else
        fout << -1;
    
    fin.close();
    fout.close();
    
    return 0;
}