Cod sursa(job #838997)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 21 decembrie 2012 00:02:06
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<cstdio>
#include<vector>
#define NMax 100005
using namespace std;

int k,ccl[NMax],grd[NMax],n;
vector <int> a[NMax];

int eulerian ()
{
    int i;
    for (i=1; i<=n; i++)
        if (grd[i]%2)
            return 0;
    return 1;
}

void euler (int nod)
{
    while (a[nod].size())
    {
        int x=a[nod].back();
        a[nod].pop_back();
        for (vector<int>::iterator it=a[x].begin(); it!=a[x].end(); it++)
            if (*it==nod)
            {
                a[x].erase(it);
                break;
            }
        euler(x);
    }
    ccl[++k]=nod;
}

int main ()
{
    int m,i,x,y;
    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);
        grd[x]++; grd[y]++;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    if (!eulerian())
        printf("-1\n");
    else
    {
        euler(1);
        for (i=1; i<=k; i++)
            printf("%d ",ccl[i]);
    }
    return 0;
}