Cod sursa(job #2572641)

Utilizator nTropicManescu Bogdan Constantin nTropic Data 5 martie 2020 13:40:07
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda OJI 2020 Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

const int len = 500005;
int n, m, x, y;
bool seen[len];
vector<pair<int, int> > g[len];
vector<int> sol;

void dfs(int node) {
    while (g[node].size()) {
        pair<int, int> curr = g[node].back();
        g[node].pop_back();
        if (!seen[curr.first]) {
            seen[curr.first] = true;
            dfs(curr.second);
        }
    }
    sol.push_back(node);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        g[x].push_back({i, y});
        g[y].push_back({i, x});
    }

    for (int i = 0; i < n; i++)
        if (g[i].size() & 1)
            return cout << "-1\n", 0;

    dfs(1);

    for (unsigned i = 0; i < sol.size(); i++)
        cout << sol[i] << " ";
}