Cod sursa(job #1626654)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 3 martie 2016 10:59:26
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

struct Data {
    int adj, edge;
    Data *nxt;
    Data() {
        nxt = NULL;
    }
    Data(int adj, int edge) {
        this->adj = adj;
        this->edge = edge;
        nxt = NULL;
    }
};

class List {

public:

    Data *p, *u;

    List() {
        p = u = NULL;
    }

    void push(int adj, int edge) {

        if (p == NULL) {
            p = new Data(adj, edge);
            u = p;
            return;
        }

        Data *aux = u;
        u = new Data(adj, edge);

        aux->nxt = u;

    }

    void pop(void) {

        if (p == NULL)
            return;

        Data *aux = p->nxt;
        delete p;
        p = aux;

    }

    void makeCyclic(void) {

        pop();
        u->nxt = p;

    }

} graph[100005], eulerCycle;

bool vis[100005], deleted[500005];
int deg[100005];

int entriesCount = 0;
void dfs(int node) {

    vis[node] = true;

    for (Data *it = graph[node].p; it != NULL; it = it->nxt) {

        ++entriesCount;
        if (vis[it->adj])
            continue;
        dfs(it->adj);

    }

}

void getEulerCycle(int node) {

    while (graph[node].p != NULL) {

        if (!deleted[graph[node].p->edge]) {
            deleted[graph[node].p->edge] = true;
            getEulerCycle(graph[node].p->adj);
        }

        graph[node].pop();

    }

    eulerCycle.push(node, 0);

}

int main() {

    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= m; ++i) {

        int x, y;
        fin >> x >> y;

        graph[x].push(y, i);
        graph[y].push(x, i);

        deg[x]++, deg[y]++;

    }

    dfs(1);

    for (int i = 1; i <= n; ++i) {
        if (deg[i] & 1) {
            fout << -1;
            return 0;
        }
    }

    if (entriesCount != 2 * m) {
        fout << -1;
        return 0;
    }

    getEulerCycle(1);
    eulerCycle.makeCyclic();

    for (Data *it = eulerCycle.p;;) {

        fout << it->adj << ' ';
        it = it->nxt;
        if (it == eulerCycle.p)
            break;

    }

    fout << '\n';

    return 0;

}

//Trust me, I'm the Doctor!