Cod sursa(job #2432577)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 24 iunie 2019 13:24:47
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define MAX (int)(1e5+5)
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n;
bool eulerian;
vector <int> Edge[MAX];
stack <int> Stk;
vector <int> Ans;

void read();
void solve();
void print();
void sterge_muchie(int, int);

int main(){
    read();
    solve();
    if(!eulerian){
        fout<<-1;
        return 0;
    }
    print();
    return 0;
}
void print(){
    reverse(Ans.begin(),Ans.end());
    Ans.pop_back();
    for(auto it:Ans){
        fout<<it<<' ';
    }
}
void solve(){
    int i,x,y;
    for(i=1;i<=n;++i)
        if(Edge[i].size()%2)
            return;

    Stk.push(1);
    while(!Stk.empty()){
        x=Stk.top();
        if(!Edge[x].empty()){
            y=Edge[x][0];
            sterge_muchie(x,y);
            Stk.push(y);
        }else{
            Ans.push_back(x);
            Stk.pop();
        }
    }

    eulerian=1;
}
void read(){
    int i,m,x,y;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y;
        Edge[x].push_back(y);
        Edge[y].push_back(x);
    }
}
void sterge_muchie(int a, int b){
    int i;
    Edge[a].erase(Edge[a].begin());
    for(i=0;i<Edge[b].size();++i){
        if(Edge[b][i]==a){
            Edge[b].erase(Edge[b].begin()+i);
            return;
        }
    }
}