Cod sursa(job #1757207)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 14 septembrie 2016 18:03:33
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <map>
using namespace std;

#define Nmax 100002

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

int N, M, Grad[Nmax];
vector < int > G[Nmax], Sol;
bitset < Nmax > Viz;
map < pair<int,int>, int > NrEdg;

void DFSEu( int nod ){

    vector < int > :: iterator it;

    for( it = G[nod].begin(); it != G[nod].end(); ++it ){
        if( NrEdg[{nod,*it}] > 0 ){
            NrEdg[{nod,*it}]--;
            NrEdg[{*it,nod}]--;
            DFSEu( *it );

        }
    }

    Sol.push_back( nod );
}

int vz = 0;
void DFS( int nod ){

    vz++;
    Viz[nod] = 1;

    vector < int > :: iterator it;
    for( it = G[nod].begin(); it != G[nod].end(); ++it )
        if( !Viz[*it] )
            DFS(*it);

}

bool Eulerian(){

    for( int i = 1; i <= N; ++i )
        if( Grad[i] & 1 )
            return 0;

    DFS(1);

    if( vz < N )
        return 0;

    return 1;
}

inline void AddEdge( int x, int y ){
    G[x].push_back(y);
    G[y].push_back(x);
    Grad[x]++;
    Grad[y]++;
    NrEdg[{x,y}]++;
    NrEdg[{y,x}]++;
}

int main(){

    int x, y;

    fin >> N >> M;

    while( M-- ){
        fin >> x >> y;
        AddEdge(x,y);
    }

    if( !Eulerian() ){
        fout << -1;
        return 0;
    }

    DFSEu(1);
    Sol.pop_back();

    vector < int > :: iterator it;
    for( it = Sol.begin(); it != Sol.end(); ++it )
        fout << *it << " ";

    return 0;
}