Cod sursa(job #1527931)

Utilizator 2chainzTauheed Epps 2chainz Data 18 noiembrie 2015 21:17:14
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int Nmax = 100001;
const int Mmax = 500001;
int pr[Mmax],val[Mmax],gr[Nmax];
int K,st[Nmax],S[Mmax],ans[Mmax];
int N,M;
int main(){
    in>>N>>M;
    int x,y;
    for(int i=1;i<=M;i++){
        in>>x>>y;
        pr[++K]=st[x],val[K]=y,st[x]=K;
        pr[++K]=st[y],val[K]=x,st[y]=K;
        gr[x]++,gr[y]++;
    }
    for(int i=1;i<=N;i++) if(gr[i]%2){
        out<<"-1\n";
        return 0;
    }
    S[++S[0]]=1;
    do{
        x=S[S[0]--];
        while(gr[x]){
            int y=val[st[x]];
            st[x]=pr[st[x]];
            if(val[st[y]]==x) st[y]=pr[st[y]];
            else{
                int p=st[y],e=0;
                while(val[p]!=x) e=p,p=pr[p];
                pr[e]=pr[pr[e]];
            }
            gr[x]--,gr[y]--;
            S[++S[0]]=x;
            x=y;
        }
        ans[++ans[0]]=x;
    }while(S[0]);
    for(int i=1;i<ans[0];i++) out<<ans[i]<<' ';
    return 0;
}