Cod sursa(job #2156335)

Utilizator amaliarebAmalia Rebegea amaliareb Data 8 martie 2018 17:37:55
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
const int MaxN = 100005, MaxM = 500005;
int n, m;
bitset<MaxM> viz;
vector<pair<int, int> > gr[MaxN];
vector<int> ans;

void euler(int node) {
    while (!gr[node].empty() && viz[gr[node].back().second] == 1) gr[node].pop_back();
    if (!gr[node].empty()) {
        pair<int, int> son = gr[node].back();
        viz[son.second] = 1;
        euler(son.first);
    }
    ans.push_back(node);
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        f >> x >> y;
        gr[x].push_back({y, i});
        gr[y].push_back({x, i});
    }
    for (int i = 1; i <= n; ++i) if (gr[i].size() % 2) {
        g << -1 << '\n';
        return 0;
    }
    euler(1);
    ans.pop_back();
    for (auto x: ans) g << x << ' ';
    return 0;
}