Cod sursa(job #1964806)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 13 aprilie 2017 18:11:36
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <list>

using namespace std;

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

int n,m;
bool U[100005];
bool UE[500005];
vector<pair<int,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,i});
        L[y].push_back({x,i});
    }
}
void dfs(int nod){
    U[nod]=1;
    for(auto x : L[nod])
        if(!U[x.first])
            dfs(x.first);
}
void euler(int st){
    int nod,vecin,id;
    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().first;
            id=L[nod].back().second;
            L[nod].pop_back();
            if(!UE[id]){
                UE[id]=1;
                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;
}