Cod sursa(job #1457534)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 3 iulie 2015 16:27:09
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
/*
    If you can't explain it simply, you don't understand it well enough.
*/
#include <cstdio>
#include <vector>

using namespace std;

const int Nmax = 100010;

int n , m , i , x , y , ok;

vector < int > g[Nmax] , ans;
vector < int > :: iterator it;

void euler(int node)
{
    int link;
    if (g[node].size()) link = g[node].back();
    while (g[node].size())
    {
        g[node].pop_back();
        for (it = g[link].begin(); it != g[link].end(); ++it)
            if (*it == node)
            {
                g[link].erase(it);
                break;
            }

        euler(link);

        if (g[node].size())
            link = g[node].back();
    }
    ans.push_back(node);
}

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

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

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

    for (i = 1; i <= n; ++i)
        if ((int)g[i].size()&1)
        {
            printf("-1\n");
            return 0;
        }

    euler(1);

    for (i = 0; i <  ans.size() - 1; ++i)
        printf("%d ", ans[i]);

    return 0;
}