Cod sursa(job #1805866)

Utilizator AndreiITCuriman Andrei AndreiIT Data 14 noiembrie 2016 16:04:07
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
/**
    code by purplecoder
*/

#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

const int MAX = 1e5 + 5;
int n, m;
stack < int > s;
vector < int > sol, gr[MAX];

void euler(){
    s.push(1);
    while(!s.empty()){
        int nod = s.top();
        if(gr[nod].size()){
            int fiu = gr[nod][ gr[nod].size() - 1 ];
            gr[nod].pop_back();
            gr[fiu].erase( find( gr[fiu].begin(), gr[fiu].end(), nod ) );
            s.push(fiu);
        }
        else{
            sol.push_back(s.top());
            s.pop();
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=m; ++i){
        int a, b;
        cin>>a>>b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    euler();
    if(sol[0] == sol[ sol.size() - 1 ] and sol.size() == m + 1){
        for(int i=0; i<sol.size() - 1; ++i)
            cout<<sol[i]<<' ';
    }
    else
        cout<<-1;
    return 0;
}