Cod sursa(job #2817409)

Utilizator andreea.ioanaSora Andreea-Ioana andreea.ioana Data 13 decembrie 2021 17:12:43
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <pair <int, int>> v[100003];
vector <int> vizitat(100003, 0);
int rez[100003], contor = 0;

void cicluEuler (int nod)
{
    int nodVecin, indice;
    while (!v[nod].empty())
    {
        nodVecin = v[nod].back().first;
        indice = v[nod].back().second;
        v[nod].pop_back();
        if (vizitat[indice] == 0)
        {
            vizitat[indice] = 1;
            cicluEuler(nodVecin);
        }
    }
    contor++;
    rez[contor] = nod;
}

int main()
{
    int n, m, st, dr, grade[100003];
    ifstream fin("ciclueuler.in");
    ofstream fout("ciclueuler.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr;
        v[st].push_back(make_pair(dr, i));
        v[dr].push_back(make_pair(st, i));
        grade[st]++;
        grade[dr]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (grade[i] % 2 == 1)
        {
            fout << -1;
            return 0;
        }
    }
    cicluEuler(1);
    for (int i = 1; i < contor; i++)
        fout << rez[i] << " ";
    fin.close();
    fout.close();
    return 0;
}