Cod sursa(job #2124877)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 7 februarie 2018 18:09:14
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#define N 500005

using namespace std;

struct muchie
{
    int x, y, viz;
}mc[N];


int n, m, sol[N];
vector <int> g[N];
stack <int> d;

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d\n", &mc[i].x, &mc[i].y);
        mc[i].viz=0;
        g[mc[i].x].push_back(mc[i].y);
        g[mc[i].y].push_back(mc[i].x);
    }
}

int verif_euler()
{
    for(int i=1;i<=n;i++)
        if(g[i].size()%2==1)
            return 0;
    return 1;
}

void parcurgere()
{
    d.push(1);
    while(!d.empty())
    {
        int nod=d.top();
        if(g[nod].size())
        {
            int urm=g[nod].back();
            g[urm].pop_back();
            if(mc[urm].viz==1)
            {
                mc[urm].viz=1;
                if(mc[urm].x==urm)
                    d.push(mc[urm].y);
                else
                    d.push(mc[urm].x);
            }
        }
        else
        {
            sol[++sol[0]]=d.top();
            d.pop();
        }
    }
}

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

    citire();
    if(!verif_euler())
        printf("-1");
    else
    {
        parcurgere();
        for(int i=0;i<sol[0];i++)
            printf("%d ", sol[i]);
    }
    return 0;
}