Cod sursa(job #2931770)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 31 octombrie 2022 21:48:02
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <bitset>

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)
{
   for (auto it : g[nod])
   {
       if (!viz[it.second])
       {
           viz[it.second] = 1;
           dfs (it.first);
       }

   }
    sol.push_back(nod);
}

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