Cod sursa(job #2576422)

Utilizator victorzarzuZarzu Victor victorzarzu Data 6 martie 2020 19:17:07
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define edge pair<int,int>
#define nod first
#define nr second
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n, m, x, y;
vector<int> c;
vector<edge> graf[100005];
bool eliminat[500005];

void Read()
{
    f>>n>>m;
    for(int i = 1;i <= m;++i)
    {
        f>>x>>y;
        graf[x].push_back({y, i});
        graf[y].push_back({x, i});
    }
}

bool ok()
{
    for(int i = 1;i <= n;++i)
        if(graf[i].size() % 2 == 1)
            return false;
    return true;
}

void ciclu()
{
    stack<int> v;
    v.push(1);

    while(!v.empty())
    {
        int nod = v.top();

        if(!graf[nod].empty())
        {
            edge muchie = graf[nod].back();
            graf[nod].pop_back();

            if(!eliminat[muchie.nr])
            {
                eliminat[muchie.nr] = true;
                v.push(muchie.nod);
            }
        }
        else
        {
            v.pop();
            c.push_back(nod);
        }
    }
}

int main()
{
    Read();
    if(!ok())
    {
        g<<-1<<'\n';
        return 0;
    }
    ciclu();
    for(int i = 0;i < c.size();++i)
        g<<c[i]<<" ";
    return 0;
}