Cod sursa(job #718683)

Utilizator mytzuskyMihai Morcov mytzusky Data 20 martie 2012 23:19:46
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <stdio.h>
#include <stack>
#include <queue>
#include <list>

#define nn 100010

using namespace std;

list  <int> G[nn];
list  <int> L;
stack <int> S;

int n, m, grad[nn], viz[nn];

void citire(){
    scanf("%d %d",&n, &m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
        grad[x]++; grad[y]++;
    }
}

void visit(int x) {
    for( typeof(G[x].begin()) it = G[x].begin() ; it != G[x].end() ; ++it )
        if( !viz[*it] )
        {
            viz[*it] = 1;
            visit(*it);
        }
}

int check_eulerian(){
    visit(1);

    for( int i=1;i<=n;++i )
        if( !viz[i] || grad[i]%2==1 )
            return 0;
    return 1;
}

void sterg(int x, int y){
    G[x].pop_front();
    grad[x]--; grad[y]--;
    for( typeof(G[y].begin()) it = G[y].begin() ; it != G[y].end() ; ++it )
        if( *it == x )
        {
            G[y].erase(it);
            return;
        }
}

void eulerian( int nod ){
    int next;
    while( ! G[nod].empty() )
    {
        next = G[nod].front();
        S.push(nod);
        sterg(nod, next);
        nod = next;
    }
}


void solve()
{
    int ok = check_eulerian();
    if(ok)
    {
        int x = 1;
        do
        {
            eulerian(x);
            x = S.top();
            S.pop();
            L.push_front(x);
        } while( !S.empty() );

        for( typeof(L.begin()) it = L.begin() ; it != L.end() ; ++it )
            printf("%d " ,*it);
    }
    else
        printf("-1");
}

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

    citire();
    solve();

    return 0;
}