Cod sursa(job #2172235)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 15 martie 2018 15:43:06
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define N 100001

using namespace std;

ifstream fin("ciclueuler.in") ;
ofstream fout("ciclueuler.out") ;

vector<int> graf[N] ;
int grad[N], sos[N] , dest[N] ;
bool viz[N] ;
int n , m;
vector<int> sol;

void citire()
{
    int i , x , y ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y ;
        graf[x].push_back(i) ;
        graf[y].push_back(i) ;
        grad[x]++ ;
        grad[y]++ ;
        sos[i] = x;
        dest[i] = y;
    }
}

void euler (int nod)
{
    int fiu ;
    while(!graf[nod].empty())
    {
        fiu = graf[nod].back() ;
        graf[nod].pop_back();
        if ( viz[fiu] == false )
        {
            viz[fiu] = true ;
            if ( sos[fiu] == nod )
                euler(dest[fiu]) ;
            else
                euler(sos[fiu]) ;
        }
    }
    sol.push_back(nod) ;
}

int main()
{
    int i ;
    citire() ;
    for ( i = 1 ; i <= n ; i++ )
    {
        if ( grad[i]%2 == 1 )
        {
            fout <<"-1" ;
            return 0;
        }
    }
    euler(1) ;
    for ( i = 0 ; i < sol.size()-1 ; i++ )
        fout << sol[i] << " " ;
}