Cod sursa(job #1552252)

Utilizator felixiPuscasu Felix felixi Data 17 decembrie 2015 16:38:58
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100000;

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

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 );
        ++ggr[x];
        ++ggr[y];
    }
    int ok = 1;
    for( int i = 1;   i<= N;  ++i ) {
        if( ggr[i] % 2 == 1 )  ok = 0;
    }
    if( !ok ) {
        out << "-1\n";
        return 0;
    }
    st.push(1);
    while( !st.empty() ) {
        int nod = st.top();

        if( G[nod].size() ) {
            int x = G[nod].back();

            st.push( x );
            G[nod].pop_back();
            G[x].erase( find( G[x].begin(), G[x].end(), nod ) );
        }
        else {
            nod = st.top();

            sol.push_back( nod );
            st.pop();
        }
    }

    ok = 0;
    vector <int> :: iterator it;
    for( it = sol.begin();  it != sol.end();  ++it ) {
        if( !ok )  ok = 1;
        else out << *it << ' ';
    }
    out << '\n';

    return 0;
}