Cod sursa(job #1541774)

Utilizator felixiPuscasu Felix felixi Data 4 decembrie 2015 15:50:50
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 100000;

vector <int> G[NMAX+2], Ans;
int gr[NMAX+2];
int N, M;

void Euler( int nod ) {
    Ans.push_back( nod );
    int i = (int)G[nod].size() - 1;
    if( i < 0 )  return;

    int x = G[nod][i];
    G[nod].pop_back();
    G[ x ].erase( find( G   [ x ].begin(),G[ x ].end(), nod ) );

    G[nod].shrink_to_fit();
    G[ x ].shrink_to_fit();

    Ans.shrink_to_fit();

    Euler( x );
}


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 );
        gr[x]++;
        gr[y]++;
    }
    int ind = 1;
    for( int i = N;  i >= 1;  --i ) {
        if( gr[i] > 0 )  ind = i;

        if( gr[i] % 2 == 1 ) {
            out << "-1\n";
        }
    }
    Euler( ind );
    for( int i = 0;  i < (int)Ans.size();  ++i ) {
        out << Ans[i] << ' ';
    }
    out << '\n';

    return 0;
}