Cod sursa(job #794810)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 octombrie 2012 00:54:23
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <stack>

#define x first
#define e second

using namespace std;

const int MaxN = 100005;
const int MaxM = 500005;

vector< pair<int, int> > G[MaxN];
int N, M, Degree[MaxN];
stack<int> Stack, Cycle;
bool Erased[MaxM], Used[MaxN], Sol;

inline int GetDegree(int X) {
    for (; Degree[X] && Erased[G[X][Degree[X]-1].e]; --Degree[X]);
    return Degree[X];
}

inline void Euler(int X) {
    for (int Y; GetDegree(X); X = Y) {
        Stack.push(X);
        Y = G[X][Degree[X]-1].x;
        Erased[G[X][Degree[X]-1].e] = true;
    }
}

inline void EulerianCycle(int X) {
    do {
        Euler(X);
        X = Stack.top(); Stack.pop();
        Cycle.push(X), Used[X] = true;
    } while (!Stack.empty());
}

inline bool EulerianGraph() {
    for (int X = 1; X <= N; ++X)
        if (G[X].size()&1)
            return false;
    return true;
}

void Solve() {
    Sol = true;
    if (!EulerianGraph()) {
        Sol = false;
        return;
    }
    EulerianCycle(1);
    for (int X = 1; X <= N; ++X)
        Sol &= Used[X];
}

void Read() {
    freopen("ciclueuler.in", "r", stdin);
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        int X, Y; scanf("%d %d", &X, &Y);
        G[X].push_back(make_pair(Y, i)), G[Y].push_back(make_pair(X, i));
        ++Degree[X], ++Degree[Y];
    }
}

void Print() {
    freopen("ciclueuler.out", "w", stdout);
    if (!Sol) {
        printf("-1\n");
        return;
    }
    for (; !Cycle.empty(); Cycle.pop())
        printf("%d ", Cycle.top());
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}