Cod sursa(job #2032961)

Utilizator JakeGyllenhaalJake Gyllenhaal JakeGyllenhaal Data 5 octombrie 2017 22:01:45
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

int n, m;
int         d[NMAX];
vector<int> g[NMAX];
vector<int> sol, stk;

void euler(int u) {
    stk.push_back(u);
    int v;

    while(!stk.empty()) {
        u = stk.back();
        if(!g[u].empty()) {
            v = g[u].back();

            g[u].pop_back();
            g[v].erase( find(g[v].begin(), g[v].end(), u) );

            stk.push_back(v);
        }
        else {
            sol.push_back(u);
            stk.pop_back();
        }
    }
}

int main(void) {
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    int a, b, anf;

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

    for(int i=1; i<=n; ++i) {
        if(d[i]%2) {
            printf("-1\n");
            return 0;
        }
        if(d[i])
            anf = i;
    }

    euler(anf);

    for(int i=1; i<sol.size(); ++i)
        printf("%d ",sol[i]);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}