Cod sursa(job #2450189)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 22 august 2019 12:01:37
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N=100000+7;
int n,m;
int sum[5*N];
bool ok[5*N];
vector <int> id[N];
int sol[5*N],top;

void rec(int a)
{
        while(!id[a].empty())
        {
                int i=id[a].back();
                id[a].pop_back();
                if(ok[i])
                {
                        ok[i]=0;
                        rec(sum[i]-a);
                }
        }
        sol[++top]=a;
}

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

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

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


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

        return 0;
}