Cod sursa(job #1197794)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 13 iunie 2014 20:16:19
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>

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

using namespace std;

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

void euler(int Nod){
    while(poz[Nod] < Graph[Nod].size()){
        if(Viz[Graph[Nod][poz[Nod]]] == 1)
            ++poz[Nod];
        else{
            int X = Graph[Nod][poz[Nod]];
            int Neighbour = Edges[X].x + Edges[X].y - Nod;
            Viz[Graph[Nod][poz[Nod]]] = 1;
            ++poz[Nod];
            euler(Neighbour);
        }
    }
    Sol.push_back(Nod);
}

int main(){
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i){
        int X, Y;
        scanf("%d %d", &X, &Y);
        Edges[i] = make_pair(X, Y);
        Graph[X].push_back(i);
        Graph[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)
        printf("%d ", Sol[i]);
    return 0;
}