Cod sursa(job #2931773)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 31 octombrie 2022 21:58:09
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <bitset>
#pragma optimize GCC ("Ofast")

using namespace std;

ifstream cin ("ciclueuler.in");
ofstream cout ("ciclueuler.out");

using mancare = pair<int, int>;

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

bitset <M + 1> viz;

vector <mancare> g[N + 1];

vector <int> sol;

int n, m, x, y, k;

void dfs (int nod)
{
    if (!g[nod].empty())
        for (auto it : g[nod])
            if (!viz[it.second])
            {
                viz[it.second] = 1;
                dfs (it.first);
            }
    sol.push_back(nod);
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (cin >> n >> m; m && cin >> x >> y; --m)g[x].push_back ({y, ++k}), g[y].push_back({x, k});
    for (int i = 1; i <= n; ++i)
        if (g[i].size() & 1)
        {
            cout << "-1\n";
            return 0;
        }
    int ind = 1;
    while (g[ind].empty())++ind;
    dfs (ind);
    sol.erase (sol.end() - 1);
    for (auto it : sol)cout << it << ' ';
    return 0;
}