Cod sursa(job #460750)

Utilizator BitOneSAlexandru BitOne Data 3 iunie 2010 20:13:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#define Nmax 100111

/*
 *
 */
using namespace std;
int d[Nmax];
vector< int > S, r;
vector< int > G[Nmax];
vector< int >::iterator it, iend;
inline void DFS( int x )
{
    int w;
    while( !G[x].empty() )
    {
        it=G[x].begin();
        w=*it;
        G[x].erase(it);
        G[w].erase( find( G[w].begin(), G[w].end(), x ) );
        S.push_back(x);
        x=w;
    }
}
inline bool IsNC( int N )
{
    int x, j=1;
    vector< bool > uz( N+1 );
    uz[1]=true;
    for( S.push_back(1); !S.empty(); )
    {
        x=S.back(); S.pop_back();
        for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
            if( false == uz[*it] )
            {
                S.push_back(*it);
                ++j;
                if( N == j )
                {
                    S.clear();
                    return false;
                }
            }
    }
    return true;
}
int main( void )
{
    int N, M, x, y;
    ifstream in( "ciclueuler.in" );
    ofstream out( "ciclueuler.out" );
    for( in>>N>>M; M; --M )
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
        ++d[x]; ++d[y];
    }
    for( x=1; x <= N; ++x )
        if( d[x]%2 )
        {
            out<<"-1";
            return EXIT_SUCCESS;
        }
    if( IsNC(N) )
    {
        out<<"-1";
        return EXIT_SUCCESS;
    }
    x=1;
    do
    {
        DFS(x);
        x=S.back(); S.pop_back();
        r.push_back(x);
    }while( !S.empty() );
    copy( r.rbegin(), r.rend(), ostream_iterator<int>( out, " " ) );
    out<<'\n';
    return EXIT_SUCCESS;
}