Cod sursa(job #3128305)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 9 mai 2023 10:50:20
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("ciclueuler.in");
ofstream g ("ciclueuler.out");

const int nmax = 1e5 + 3;
int viz[5 * nmax], sol[5 * nmax], k, n, m, x, y, grad[nmax];
vector <pair <int, int> > v[nmax];

void dfs(int nod)
{
    while (!v[nod].empty())
    {
        while (!v[nod].empty() && viz[v[nod].back().first])
            v[nod].pop_back();

        if (v[nod].empty())
            break;

        int urm = v[nod].back().second;

        viz[v[nod].back().first] = 1;
        dfs(urm);
    }

    sol[++k] = nod;
}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y;
        v[x].push_back(make_pair(i, y));
        v[y].push_back(make_pair(i, x));
        ++grad[x];
        ++grad[y];
    }

    for (int i = 1; i <= n; ++i)
    {
        if (grad[i] & 1)
        {
            g << -1;
            return 0;
        }
    }

    dfs(1);

    for (int i = 1; i <= k; ++i)
        g << sol[i] << ' ';

    return 0;
}