Cod sursa(job #1602990)

Utilizator DysKodeTurturica Razvan DysKode Data 17 februarie 2016 08:55:03
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iostream>
#include <vector>

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 ].begin();
        k = *it;
        Graf[ nod ].erase( it );
        --EXT[ nod ];
        for( vector<int>::iterator itB = Graf[ k ].begin() ; itB != Graf[ k ].end() ; itB++ )
        {
            if( *itB == nod )
            {
                --INT[ *itB ];
                Graf[ k ].erase( itB );
                break;
            }
        }
        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 );
        EXT[ x ]++;
        INT[ y ]++;
    }

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

    euler( 1 );

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

return 0;
}