Cod sursa(job #3182817)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 9 decembrie 2023 17:37:39
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1e5;
const int MMAX = 5e5;

int n, m, ind;
vector<pair<int, int>> G[NMAX + 1];
int cycle[MMAX + 1];
bool used[MMAX + 1];

void Read()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back({y, i});
        G[y].push_back({x, i});
    }
}

void DFS(int node)
{
    while(!G[node].empty())
    {
        auto edge = G[node].back();
        G[node].pop_back();

        if(!used[edge.second])
        {
            used[edge.second] = 1;
            DFS(edge.first);
        }
    }

    cycle[++ind] = node;
}

void Solve()
{
    for(int i = 1; i <= n; i++)
        if(G[i].size() % 2 == 1)
        {
            cout << -1;
            return;
        }

    DFS(1);
    for(int i = 1; i < ind; i++)
        cout << cycle[i] << ' ';
}


int main()
{
    Read();
    Solve();

    return 0;
}