Cod sursa(job #1788352)

Utilizator enescu_rEnescu Radu enescu_r Data 25 octombrie 2016 22:07:20
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100005;
const int MMAX = 500005;
vector <int> G[NMAX];
int N, M, i, x, y, k, nr;
int ST[MMAX], EULER[MMAX];

void sterge(int x, int y)
{
    for (int i = 0; i < G[x].size(); i++)
        if (G[x][i] == y)
        {
            swap(G[x][i],G[x][G[x].size()-1]);
            G[x].pop_back();
            return ;
        }
}

void euler()
{
    while (k > 0)
    {
        if (G[ST[k]].size()>0)
        {
            x = G[ST[k]][0];
            sterge(x,ST[k]);
            sterge(ST[k],x);
            k++;
            ST[k] = x;
        }
        else
        {
            --k;
            if (k>0)
            {
                nr++;
                EULER[nr]= ST[k];
            }
        }
    }
}
int main()
{
    freopen("ciclueuler.in", "r" , stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d%d\n", &N, &M);
    for (i = 1; i <= M; i++)
    {
        scanf("%d%d\n", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (i = 1; i <= N; i++)
        if (G[i].size()%2==1)
    {
        printf("-1\n");
        return 0;
    }
    k = 1;
    ST [k] = 1;
    nr = 0;
    euler ();
    for (i = 1; i <= nr; i++)
        printf("%d ", EULER[i]);
    return 0;
}