Cod sursa(job #1756419)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 12 septembrie 2016 20:00:16
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#define N 110000

using namespace std;

vector<int > muc[N];
vector< int >::iterator it ;
stack <int> stk;
int n,m;

void citire(){
    static int i,x,y;

    scanf("%d%d",&n,&m);

    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        muc[x].push_back( y );
        muc[y].push_back( x );
    }
}

bool verif(){
    static int i;

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

void erasemuc(int x,int y){
    vector< int >::iterator itmuc ;
    static int nr;

    muc[x].erase( muc[x].begin());

    for(itmuc=muc[y].begin(),nr=0; itmuc!=muc[y].end(); itmuc++,nr++){
        if(*itmuc==x){
            muc[y].erase(muc[y].begin()+nr );
            return ;
        }
    }

}

int main(){
    int nod,temp;

    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    citire();

    if(verif()==0){
        printf("-1");
        return 0;
    }

    stk.push(1);

    while(!stk.empty()){
        nod=stk.top();
        stk.pop();

        for(it=muc[nod].begin(); it!=muc[nod].end();){

            temp=nod;
            stk.push(temp);
            nod=*it;
            it=muc[nod].begin();

            erasemuc(temp,nod);


        }
        printf("%d ",nod);

    }

    return 0;
}