Cod sursa(job #2416125)

Utilizator eduardcadarCadar Eduard eduardcadar Data 26 aprilie 2019 22:15:14
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
#define nmax 100005
int n, m, x, y;
vector<int> v[nmax];
vector<int> s, sol;
void euler() {
    while (!s.empty()) {
        int nod = s.back();
        if (!v[nod].empty()) {
            int w = v[nod].back();
            v[nod].pop_back();
            for (int i = 0; i < v[w].size(); ++i)
                if (v[w][i] == nod) {
                    swap(v[w][i],v[w][v[w].size()-1]);
                    v[w].pop_back();
                    break;
                }
            s.push_back(w);
        }
        else {
            s.pop_back();
            sol.push_back(nod);
        }
    }
}
int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        f >> x >> y;
        v[x].push_back(y), v[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i)
        if (v[i].size() & 1) { g << "-1\n"; return 0; }
    s.push_back(1);
    euler();
    for (int i = 0; i < sol.size() - 1; ++i) g << sol[i] << ' ';
    g << '\n';
    return 0;
}