Cod sursa(job #1624549)

Utilizator DysKodeTurturica Razvan DysKode Data 2 martie 2016 11:55:39
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

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

    while( Graf[ nod ].size() )
    {
        it = Graf[ nod ].begin();
        k = *it;
        Graf[ nod ].erase( it );
        for( vector<int>::iterator itB = Graf[ k ].begin() ; itB != Graf[ k ].end() ; itB++ )
        {
            if( *itB == nod )
            {
                Graf[ k ].erase( itB );
                break;
            }
        }
        euler( k );
    }
    ans.push_back( nod );
}

void dfs( int nod )
{
    use[ nod ] = 1;
    for( auto it : Graf[ nod ] )
        if( !use[ it ] )
            dfs( it );
}

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 ]++;
        }
    }

    dfs( 1 );

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

    ST.push( 1 );
    while(  )
    {
        nod = ST.top();
        ST.pop();
        vector< int >::iterator it;
        int k;

        while( Graf[ nod ].size() )
        {
            it = Graf[ nod ].begin();
            k = *it;
            Graf[ nod ].erase( it );
            for( vector<int>::iterator itB = Graf[ k ].begin() ; itB != Graf[ k ].end() ; itB++ )
            {
                if( *itB == nod )
                {
                    Graf[ k ].erase( itB );
                    break;
                }
            }
            ST.push( k );
        }
        ans.push_back( nod );
    }

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

return 0;
}