Cod sursa(job #1316525)

Utilizator gerd13David Gergely gerd13 Data 13 ianuarie 2015 21:34:15
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <math.h>
#include <algorithm>
#include <bitset>

#define pb push_back
#define x first
#define y second

using namespace std ;

const int NMAX = 500005 ;
const int INF = 0x3f3f3f3f ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> Pair ;

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

int N, M ;

void READ() ;
void SOLVE() ;
void OUT() ;
void EULER(int) ;
bool CEUlER() ;
void DFS(int) ;


bool visited[NMAX] ;
vector <int> sol ;
stack <int> S ;
vector <int> V[NMAX] ;
int PAR[NMAX] ;

inline void READ()
{
    fin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {
        int X, Y ;

        fin >> X >> Y ;

        V[X].pb(Y) ;
        V[Y].pb(X) ;
        PAR[X] ++ ;
        PAR[Y] ++ ;

    }

}


 void DFS(int node)
{
    visited[node] = true ;

    for( unsigned i = 0 ; i < V[node].size() ; ++ i)
    {
        int neighbor = V[node][i] ;

        if(!visited[neighbor])
            DFS(neighbor) ;

    }

}



bool CEUlER()
{


    for(int i = 1 ; i <= N ; ++ i)
        if( !visited[ i ] || PAR[i] % 2 != 0 )
            return false ;

    return true ;
}


inline  void EULER(int v)
{
    while(1)
    {

        if( V[v].empty() )
            break ;

        int w = V[ v ][ V[v].size() - 1 ] ;

        for(unsigned i = 0 ; i < V[w].size() ; i ++)
            if(V[w][i] == v)
            {
                V[w].erase( V[w].begin() + i) ;
            break ;
            }

      v = w ;}


}

inline void SOLVE()
{
     DFS(1) ;

     if(CEUlER())
     {
         int v = 1 ;

         do {

           EULER(v) ;

           v = S.top() ;
           S.pop() ;
           sol.pb(v) ;


         }while( !S.empty() ) ;

         for(unsigned i = 0 ; i < sol.size() ; ++ i)
            fout << sol[i] << ' ' ;

     }

     else fout << "-1\n" ;

}

int main()
{

    READ() ;
    SOLVE() ;

    fin.close() ;
    fout.close() ;
    return  0 ;
}