Cod sursa(job #1508367)

Utilizator MKLOLDragos Ristache MKLOL Data 22 octombrie 2015 15:25:24
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<iostream>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define Nmax 101010


using namespace std;
vector<int> ret;
vector<pair<int,int> > g[Nmax];
int isD[Nmax*5];
int N,M,k,nrComp;
int myStack[Nmax*5];
int myStackV[Nmax*5];
void do_algo(){
    myStack[0] = 1; k = 0;
    while(k >= 0) {
        int x = myStack[k];
        int rec = 1;
        while(myStackV[k] < g[x].size()) {
            auto n = g[x][myStackV[k]];
            if(isD[n.sc]==0){
                isD[n.sc]=1;
                myStack[++k] = n.fs;
                myStackV[k] = 0;
                rec = 0;
            }
            if(rec) {
                ++myStackV[k];
            } else break;
        }
        if (rec) {
            --k;
            ret.pb(x);
        }
    }
}
int main(){
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].pb(mp(y,i));
        g[y].pb(mp(x,i));
    }
    int ok=1;
    for(int i=1;i<=N;++i){
        if(g[i].size() % 2 == 1){
            ok=0;
        }
    }
    if(ok)
    do_algo();
    //cout << "X" << endl;
    if(ret.size() != M+1)
        ok=0;
    if(ok==0){
        printf("-1");
        return 0;
    }
    for(auto x : ret){
        printf("%d ", x);
    }
    return 0;
}