Cod sursa(job #1156335)

Utilizator teoionescuIonescu Teodor teoionescu Data 27 martie 2014 16:20:03
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int Nmax = 100005;
const int Mmax = 500005;
int N,M;
struct FastList{
    int to[2*Mmax],next[2*Mmax];
    int lst[Nmax],cate[Nmax];
    int many;
    void push(int x,int y){
        to[++many]=y;
        next[many]=lst[x];
        lst[x]=many;
        cate[x]++;
    }
    void erase(int x,int y){
        int p=lst[x];
        if(to[p]==y){
            lst[x]=next[p];
            return;
        }
        while(to[next[p]]!=y) p=next[p];
        next[p]=next[next[p]];
    }
    int empty(int x){
        return lst[x]==0;
    }
    int get(int x){
        return to[lst[x]];
    }
    int grad(int x){
        return cate[x];
    }
} G;
int mark[Nmax];
int S[Mmax],K;
queue<int> q;
void Bfs(){
    q.push(1);
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int p=G.lst[x];p!=0;p=G.next[p]){
            if(!mark[G.to[p]]){
                mark[G.to[p]]=1;
                q.push(G.to[p]);
            }
        }
    }
}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        G.push(x,y);
        G.push(y,x);
    }
    Bfs();
    for(int i=1;i<=N;i++){
        if(!mark[i] || G.grad(i)%2!=0){
            out<<"-1\n";
            return 0;
        }
    }
    int w=1;
    do{
        while(!G.empty(w)){
            int son=G.get(w);
            G.erase(w,son);
            G.erase(son,w);
            S[++K]=w;
            w=son;
        }
        w=S[K--];
        out<<w<<' ';
    } while(K);
    return 0;
}