Cod sursa(job #1818502)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 29 noiembrie 2016 13:01:58
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<vector>
#include<deque>

using namespace std;

int n,m,i,x,y,aux;
deque<int> q;
vector<int> g[500002],sol;

void df(int x,int y)
{
    q.push_back(y);
    for(vector<int>::iterator it=g[y].begin();it!=g[y].end();it++)
    {
        if(*it==x)
        {
            g[y].erase(it);
            break;
        }
    }
    while(g[y].size()>0)
    {
        aux=g[y].front();
        g[y].erase(g[y].begin());
        df(y,aux);
    }
    sol.push_back(q.back());
    q.pop_back();
}

int main()
{
    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);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(g[x].size()%2==1||g[x].size()==0)
        {
            printf("-1\n");
            return 0;
        }
    }
    q.push_back(1);
    i=g[1].front();
    g[1].erase(g[1].begin());
    df(1,i);
    for(i=0;i<sol.size();i++)
    {
        printf("%d ",sol[i]);
    }
}