Cod sursa(job #2232269)

Utilizator 24601Dan Ban 24601 Data 18 august 2018 13:26:16
Problema Ciclu Eulerian Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stdio.h>

#define NMAX 100000
#define MMAX 500000

static struct edge {
    int node;
    int prev, next;
    int compl;
} edges[2*MMAX+1];

static int adj[NMAX+1], sol[MMAX+1], nsol;
static int deg[NMAX+1];

static inline void ciclueuler(int v)
{
    int compl, node;

    while (adj[v] != 0) {
        compl = edges[adj[v]].compl;
        node = edges[adj[v]].node;

        adj[v] = edges[adj[v]].next;
        edges[adj[v]].prev = 0;

        if (adj[node] == compl) {
            adj[node] = edges[adj[node]].next;
            edges[adj[node]].prev = 0;
        } else {
            edges[edges[compl].prev].next = edges[compl].next;
            edges[edges[compl].next].prev = edges[compl].prev;
        }

        ciclueuler(node);
    }

    sol[nsol++] = v;
}

int main()
{
    int n, m, u, v, i;

    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; i++) {
        scanf("%d %d", &u, &v);

        edges[2*i].node = v;
        edges[2*i].next = adj[u];
        edges[2*i].prev = 0;
        edges[2*i].compl = 2*i+1;
        edges[adj[u]].prev = 2*i;
        adj[u] = 2*i;

        deg[u]++;
        deg[v]++;
        if (u != v) {
            edges[2*i+1].node = u;
            edges[2*i+1].next = adj[v];
            edges[2*i+1].prev = 0;
            edges[2*i+1].compl = 2*i;
            edges[adj[v]].prev = 2*i+1;
            adj[v] = 2*i+1;

            deg[u]++;
            deg[v]++;
        }
    }

    for (v = 1; v <= n; v++) {
        if (deg[v] % 2) {
            puts("-1");
            return 0;
        }
    }

    ciclueuler(1);

    for (i = 0; i < nsol - 1; i++) {
        printf("%d ", sol[i]);
    }

    return 0;
}