Cod sursa(job #1231543)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 20 septembrie 2014 22:18:25
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <list>
#include <queue>
#include <stdlib.h>
#include <stack>
using namespace std;
int n,m,i,x,y;
list<int> L[100002],T;
int deg[100002],col[100002];
queue<int> Q;
list<int> :: iterator it;
list<int> :: reverse_iterator it2;
stack<int> S;
 ifstream f("ciclueuler.in");
    ofstream g("ciclueuler.out");

void fin(){
    g << "-1";
    exit(0);
}

void sterge(int v,int w){
    --deg[v]; --deg[w];
    L[v].pop_front();
    for( it = L[w].begin() ; it != L[w].end() ; ++it ){
        if( *it == v ){
            L[w].erase( it );
            break;
        }
    }
}

int main()
{


    f >> n >> m;
    for(i=1;i<=m;++i){
        f >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
        ++deg[x]; ++deg[y];
    }

    int v =1,w;
    Q.push(v); col[v] = 1;
    for( ; !Q.empty(); Q.pop() ){
        v = Q.front();
        for( it = L[v].begin(); it != L[v].end(); ++it ){
            if( !col[ *it ]  ){
                col[*it] = 1;
                Q.push( *it );
            }
        }
    }
    for(i=2;i<=n;++i)
        if( col[i] == 0 )
            fin();  ///// exit
    for(i=1;i<=n;++i)
        if( deg[i] %2 )
            fin();  //// exit

    v = 1;
    do{
        while(true){
            if( L[v].empty() )
                break;
            w = L[v].front();
            S.push( v );
            sterge(v,w);
            v = w;
        }
        v = S.top(); S.pop();
        T.push_back( v );

    }while(!S.empty());
    for(it2=T.rbegin(); it2 != T.rend(); ++it2){
        g << *it2 << " ";
    }



    return 0;
}