Cod sursa(job #1603421)

Utilizator DysKodeTurturica Razvan DysKode Data 17 februarie 2016 15:22:35
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector <int> Graf[100010],ans;
int n,m,i,j,k,INT[100010],EXT[100010],x,y;

void euler( int nod )
{
    vector< int >::iterator it;
    int k;

    while( Graf[ nod ].size() )
    {
        it = Graf[ nod ].end();
        k = *it;
        Graf[ nod ].erase( it );
        Graf[ k ].erase( find( Graf[ k ].begin() , Graf[ k ].end() , nod ) );
        euler( k );
        ans.push_back( nod );
    }
}

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        Graf[ x ].push_back( y );
        Graf[ y ].push_back( x );
        if( x != y )
        {
            EXT[ x ]++;
            INT[ y ]++;
        }
    }

    for( i = 1;  i <= n ; i++ )
        if( ( INT[ i ] + EXT[ i ] ) % 2 && INT[ i ] + EXT[ i ] > 0 )
        {
            fout<<-1;
            return 0;
        }

    euler( 1 );

    for( vector< int >::iterator it = ans.begin() ; it != ans.end() ; it++ )
    {
        fout<<(*it)<<' ';
    }

return 0;
}