Cod sursa(job #2697359)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 18 ianuarie 2021 12:47:28
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>

using namespace std;

const int N = 1e5;
const int M = 5e5;

vector<int> gr[N + 1], ans;
int a[M + 1], b[M + 1], grad[N + 1];
bool viz[M + 1];

void euler(int nod) {
    while (!gr[nod].empty()) {
        int muchie = gr[nod].back();
        gr[nod].pop_back();

        if (viz[muchie])
            continue;
        viz[muchie] = true;

        if (nod == a[muchie])
            euler(b[muchie]);
        else
            euler(a[muchie]);
    }
    ans.push_back(nod);
}

int main() {
    ifstream in("ciclueuler.in");
    ofstream out("ciclueuler.out");

    int n, m;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> a[i] >> b[i];
        gr[a[i]].push_back(i);
        gr[b[i]].push_back(i);
        ++grad[a[i]];
        ++grad[b[i]];
    }
    in.close();

    for (int i = 1; i <= n; ++i)
        if (grad[i] % 2) {
            out << "-1";
            out.close();
            return 0;
        }

    euler(1);
    ans.pop_back();

    for (auto nod : ans)
        out << nod << ' ';
    out.close();
    return 0;
}