Cod sursa(job #1208743)

Utilizator xtreme77Patrick Sava xtreme77 Data 16 iulie 2014 15:06:06
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

#define rint register int
#define pb push_back

const char IN[]="ciclueuler.in";
const char OUT[]="ciclueuler.out";
const int MAX = 100100;

using namespace std;

int n;
vector <int> gr[MAX];
stack <int> st;
vector <int> sol;

void ciclu( int start );

int main( )
{
    int m ;
    freopen( IN , "r" , stdin );
    freopen( OUT , "w" , stdout );
    scanf( "%d %d" , &n , &m );
    while(m--){
        int x,y;
        scanf( "%d %d" , &x , &y );
        gr[x].pb(y);
        gr[y].pb(x);
    }
    for( rint i = 1 ; i <= n ; ++ i )
        if( gr[i].size()&1 ){
            printf("-1\n");
            return 0;
        }
    ciclu(1);
    for( rint i = 0 ; i < (int)sol.size( ) ; ++ i )
        printf("%d ",sol[i]);
    printf("\n");
    return 0;
}
void ciclu( int start )
{
    st.push(start);
    while( !st.empty( ) ){
        int nod = st.top( );
        if( gr[nod].size( ) ){
            int last=gr[nod].back();
            gr[nod].pop_back();
            st.push(last);
            gr[last].erase( find(gr[last].begin(),gr[last].end(),nod) );
        }
        else sol.pb(nod),st.pop();
    }
}