Cod sursa(job #3167779)

Utilizator Rux099Vasilescu Ruxandra Rux099 Data 11 noiembrie 2023 09:07:51
Problema Ciclu Eulerian Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <map>

using namespace std;

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

const int nmax = 100005;
struct muchii
{
    int st, dr;
}A[nmax];

int n, m, Q[nmax], k, nr;
map< int, map<int, int> > M;

void euler(int x)
{
    for(int i = 1; i <= n; i ++)
        if(M[i][x])
        {
            M[i][x] --; M[x][i] --;
            euler(i);
        }
    Q[++ k] = x;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        f >> A[i].st >> A[i].dr;

        M[A[i].st][A[i].dr] ++;
        M[A[i].dr][A[i].st] ++;
    }

    for(int i = 1; i <= n; i ++)
    {
        int nr = 0;
        for(int j = 1; j <= n; j ++)
            nr += M[i][j];

        if(nr % 2 == 1)
        {
            g << -1;
            return 0;
        }
    }

    euler(1);
    for(int i = k; i > 1; i --)
        g << Q[i] << " ";

    return 0;
}