Cod sursa(job #2198294)

Utilizator Narvik13Razvan Roatis Narvik13 Data 24 aprilie 2018 10:27:53
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMX 100002

using namespace std;

ifstream f("ciclueuler.in");
ofstream o("ciclueuler.out");

int n,m, grad[NMX];
vector <pair<int,bool>> g[NMX];
vector <int> cicle;

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

void euler(int nod)
{
    while(g[nod].size())
    {
        while(g[nod].size() && g[nod].back().second == false)
            g[nod].pop_back();

        if(g[nod].size() == 0)
            break;

        int next = g[nod].back().first;
        g[nod].pop_back();
        //vector<pair<int,bool>>::iterator it = find(g[next].begin(), g[next].end(), {nod,true});
        //pair<int,int> t = {nod, true};
        //g[next].erase(find_if(g[next].begin(), g[next].end(), [&](pair<int,bool> p){return p.first == nod;}));
        //*it = {nod,false};
        for(vector<pair<int,bool>>::iterator it = g[next].begin(); it != g[next].end(); ++it)
            if(it->first == nod && it->second == true)
            {
                it->second = false;
                break;
            }

        euler(next);
    }
    cicle.push_back(nod);
}

void output()
{
    for(const auto& i: cicle)
        o << i << ' ';
}

int main()
{
    input();
    for(int i = 1; i <= n; ++i)
        if(grad[i] % 2 == 1)
        {
            o << -1 << '\n';
            return 0;
        }
    euler(1);
    output();
    return 0;
}