Cod sursa(job #2198576)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 24 aprilie 2018 18:38:47
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define D_MAX 100005
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
struct aparitii{
    int x;
    int i;
};
vector <aparitii> lista[D_MAX];
vector <int> ciclu,stiva;
int n,m,ap[5*D_MAX];
void Solve(int x)
{
    stiva.push_back(x);
    while(!stiva.empty())
    {
        int a=stiva.back();
        if(!lista[a].empty())
        {
            if(!ap[lista[a].back().i])
            {
                ap[lista[a].back().i]=1;
                stiva.push_back(lista[a].back().x);
            }
            lista[a].pop_back();
        }
        else
        {
            ciclu.push_back(a);
            stiva.pop_back();
        }
    }
}
int main()
{
    in >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        in >> x >> y;
        lista[x].push_back({y,i});
        lista[y].push_back({x,i});
    }
    for(int i=1; i<=n; i++)
    {
        if(!lista[i].size() || lista[i].size()%2)
        {
            cout << -1;
            return 0;
        }
    }
    Solve(1);
    for(int i=0; i<ciclu.size()-1; i++)
    {
        out << ciclu[i] << ' ';
    }
    return 0;
}