Cod sursa(job #1717641)

Utilizator felixiPuscasu Felix felixi Data 15 iunie 2016 13:47:58
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 100000;

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

vector <int> G[NMAX+2], st, sol;
int dg[NMAX+2];
int N, M;

void Euler( int nod ) {
    st.push_back( nod );
    while( st.size() ) {
        int nod = st.back();
        if( G[nod].size() ) {
            int x = G[nod].back();
            G[nod].pop_back();
            G[x].erase( find(G[x].begin(), G[x].end(), nod) );
            st.push_back( x );
        }
        else {
            sol.push_back( nod );
            st.pop_back();
        }
    }
}

int main() {
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y;
        in >> x >> y;
        G[x].push_back( y );
        G[y].push_back( x );
        ++dg[x];  ++dg[y];
    }
    int start = 1;
    for( int i = 1;  i <= N;  ++i ) {
        if( dg[i] % 2 == 1 ) {
            out << -1 << '\n';
            return 0;
        }
        if( dg[i] ) start = i;
    }
    Euler( start );
    for( int i = 1;  i < (int)sol.size();  ++i ) {
        out << sol[i] << ' ';
    }
    return 0;
}