Cod sursa(job #2185659)

Utilizator Athena99Anghel Anca Athena99 Data 24 martie 2018 18:56:06
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

const int nmax= 100000;
const int mmax= 500000;

int n, m;
int sol[mmax+1];

stack <int> s;
vector <int> g[nmax+1];

int main(  ) {
    fin>>n>>m;
    for ( int i= 1, x, y; i<=m; ++i ) {
        fin>>x>>y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for ( int i= 1; i<=n; ++i ) {
        if ( (int)g[i].size()%2==1 ) {
            fout<<"-1\n";
            return 0;
        }
    }

    for ( s.push(1); !s.empty(); ) {
        int x= s.top();

        if ( (int)g[x].size()>0 ) {
            int y= g[x].back();

            for ( int i= 0; i<(int)g[y].size(); ++i ) {
                if ( g[y][i]==x ) {
                    g[y][i]= g[y].back();
                    g[y].pop_back();
                    break;
                }
            }
            s.push(y);
            g[x].pop_back();
        } else {
            sol[++sol[0]]= x;
            s.pop();
        }
    }

    for ( int i= 1; i<=sol[0]-1; ++i ) {
        fout<<sol[i]<<" ";
    }
    fout<<"\n";

    return 0;
}