Cod sursa(job #1111605)

Utilizator cbanu96Banu Cristian cbanu96 Data 18 februarie 2014 23:21:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <queue>

#define FILEIN "ciclueuler.in"
#define FILEOUT "ciclueuler.out"
#define NMAX 100002

using namespace std;

vector<int> A[NMAX];
bool Uz[NMAX];
queue<int> Q;
stack<int> S;
int n,m;

void bf(int nod) {
    Q.push(nod); Uz[nod] = true;
    while(!Q.empty()) {
        int x = Q.front(); Q.pop();
        for ( int i = 0; i < A[x].size(); i++ ) {
            if (!Uz[A[x][i]]) {
                Uz[A[x][i]] = true;
                Q.push(A[x][i]);
            }
        }
    }
}

bool isEuler() {
    bf(1);
    for ( int i = 1; i <= n; i++ ) {
        if (!Uz[i] || A[i].size() % 2) {
            return false;
        }
    }

    return true;
}

void removeEdge(int a, int b) {
    for ( vector<int>::iterator it = A[a].begin(); it != A[a].end(); ++it) {
        if (*it == b) {
            A[a].erase(it);
            break;
        }
    }

    for ( vector<int>::iterator it = A[b].begin(); it != A[b].end(); ++it) {
        if (*it == a) {
            A[b].erase(it);
            break;
        }
    }
}

void fillEuler(int nod) {
    while (!A[nod].empty()) {
        int x = A[nod][0];
        removeEdge(nod, x);
        S.push(nod);
        nod = x;
    }
}

vector<int> euler() {
    vector<int> sol;

    int last = 1;
    do {
        fillEuler(last);
        last = S.top(); S.pop();
        sol.push_back(last);
    } while(!S.empty());

    return sol;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &n, &m);
    for ( int i = 1, x, y; i <= m; i++ ){
        scanf("%d %d", &x, &y);
        A[x].push_back(y);
        A[y].push_back(x);
    }

    if (!isEuler()) {
        printf("-1");
        return 0;
    }

    vector<int> sol = euler();
    for ( int i = 0; i < sol.size(); i++ ) {
        printf("%d ", sol[i]);
    }
    printf("\n");

    return 0;
}