Cod sursa(job #2884056)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 2 aprilie 2022 12:37:04
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
const int N=1e5+1,M=5e5+1;
const int inf=1e9+1;
int n,m,poz[M];
bool sters[M];
pair <int,int> e[M];
vector <int> a[N],sol;
stack <int> st;

bool grad_par(){
    for(int i=1; i<=n; i++)
        if(a[i].size()%2==1)
            return 0;
    return 1;
}

int cauta_muchie(int x){
    for(int i=poz[x]; i<a[x].size(); i++)
        if(!sters[a[x][i]]){
            poz[x]=i;
            return a[x][i];
        }
    return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x,y;
        cin>>x>>y;
        e[i]={x,y};
        a[x].push_back(i);
        a[y].push_back(i);
    }
    if(!grad_par())
        cout<<"-1";
    else{
    st.push(1);
    while(!st.empty()){
        int x=st.top();
        int m=cauta_muchie(x);
        if(m==-1){
            sol.push_back(x);
            st.pop();
        }else{
            int y=e[m].first+e[m].second-x;
            st.push(y);
            sters[m]=1;
        }
    }
    for(int j:sol)
        cout<<j<<" ";
    }
    return 0;
}