Cod sursa(job #1964800)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 13 aprilie 2017 18:04:37
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

int n,m;
bool U[100005];
vector<int> L[100005];
vector<int> SOL;

void read(){
    in>>n>>m;
    for(int x,y,i=1;i<=m;i++){
        in>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
}
void dfs(int nod){
    U[nod]=1;
    for(auto x : L[nod])
        if(!U[x])
            dfs(x);
}
void euler(int st){
    int nod,vecin;
    stack<int> S;
    S.push(st);
    while(!S.empty()){
        nod=S.top();
        if(L[nod].empty()){
            S.pop();
            SOL.push_back(nod);
        }
        else{
            vecin=L[nod].back();
            L[nod].pop_back();
            L[vecin].erase(find(L[vecin].begin(),L[vecin].end(),nod));
            S.push(vecin);
        }
    }
}
void solve(){
    dfs(1);
    for(int i=1;i<=n;i++){
        if(!U[i]||L[i].size()%2!=0){
            out<<-1;
            return;
        }
    }
    euler(1);
    SOL.pop_back();
    for(auto x : SOL)
        out<<x<<" ";
}
int main(){
    read();
    solve();
    return 0;
}