Cod sursa(job #1645223)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 10 martie 2016 11:36:45
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define x first
#define y second
#define MMAX 500007
#define NMAX 100007

using namespace std;

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

pair < int, int > Edges[MMAX];
vector < int > v[NMAX], Sol;
int poz[NMAX], Ap[NMAX];
bool Viz[MMAX];
int n, m;

void euler(int Node){
    while(poz[Node] < v[Node].size()){
        if(Viz[v[Node][poz[Node]]] == 1)
            ++poz[Node];
        else{
            int Nr = v[Node][poz[Node]];
            int Vecin = Edges[Nr].x + Edges[Nr].y - Node;
            Viz[v[Node][poz[Node]]] = 1;
            ++poz[Node];
            euler(Vecin);
        }
    }
    Sol.push_back(Node);
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int X, Y;
        cin >> X >> Y;
        Edges[i] = make_pair(X, Y);
        v[X].push_back(i);
        v[Y].push_back(i);
        ++Ap[X];
        ++Ap[Y];
    }
    for(int i = 1; i <= n; ++i)
        if(Ap[i] % 2 == 1){
            printf("-1");
            return 0;
        }
    euler(1);
    for(int i = Sol.size() - 1; i >= 1; --i)
        cout << Sol[i] << " ";
    return 0;
}