Cod sursa(job #2428349)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 4 iunie 2019 21:01:02
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <cstdio>
#include <cctype>
#include <iostream>
#include <vector>

using namespace std;

const int S=(1<<17);
char buffer[S];
int ptr=S;

char advance()
{
        if(ptr==S)
        {
                fread(buffer,1,S,stdin);
                ptr=0;
        }
        return buffer[ptr++];
}

int read()
{
        int res=0;
        char ch=advance();
        while(!isdigit(ch))
        {
                ch=advance();
        }
        while(isdigit(ch))
        {
                res=10*res+ch-'0';
                ch=advance();
        }
        return res;
}

const int N=100000+7;
const int M=500000+7;

int n,m;
int sum[M];
vector <int> g[N];
bool u[M];
int stk[M],top=0;

void euler(int a)
{
        while(g[a].empty()==0)
        {
                int bk=g[a].back();
                g[a].pop_back();
                if(u[bk]==0)
                {
                        u[bk]=1;
                        euler(sum[bk]-a);
                }
        }
        stk[++top]=a;
}

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

        n=read();
        m=read();

        for(int i=1;i<=m;i++)
        {
                int x=read();
                int y=read();
                sum[i]=x+y;
                g[x].push_back(i);
                g[y].push_back(i);
        }

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

        euler(1);

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

        return 0;
}