Cod sursa(job #2209966)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 5 iunie 2018 11:38:53
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define N 100000
#define M 500000
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int nr,vf[2*M],urm[2*M],lst[N],leg[2*M],v[N],k,a[N];
bool viz[2*M];
void dfs(int x)
{
    int p=lst[x],y;
    while(p)
    {
        y=vf[p];
        if(!viz[leg[p]])
        {
            viz[leg[p]]=1;
            dfs(y);
        }
        p=urm[p];
    }
    v[k++]=x;
}
void ad(int x,int y)
{
	vf[++nr]=y;
	urm[nr]=lst[x];
	leg[nr]=k;
	lst[x]=nr;
}
int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    for(i=1;i<=m;i++,k++)
    {
        in>>x>>y;
        ad(x,y);
        a[x]++;
        if(x!=y)
            ad(y,x);
        a[y]++;
    }
    for(i=1;i<=n;i++)
        if(a[i]%2)
        {
            out<<-1;
            return 0;
        }
    k=0;
    dfs(1);
    for(i=0;i<k-1;i++)
        out<<v[i]<<" ";
    return 0;
}