Cod sursa(job #2907756)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 31 mai 2022 16:18:16
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n;
int m;
vector<vector<int>>vecini;
vector<int>de_afisat;

void euler(int nod){

    while(!vecini[nod].empty()){
        int vecin_nod = vecini[nod].back();
        vecini[nod].pop_back();

        for(int i = 0; i < vecini[vecin_nod].size(); i++)
            if(vecini[vecin_nod][i] == nod){
                vecini[vecin_nod][i] = vecini[vecin_nod].back();
                vecini[vecin_nod].pop_back();
                break;
            }

        euler(vecin_nod);
    }

   de_afisat.push_back(nod);
}


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

   vecini.resize(n + 1);

   for(int i = 0; i < m; i++){

        int u, v;

        f >> u >> v;

        vecini[u].push_back(v);
        vecini[v].push_back(u);
   }

   for(int i = 1; i <= n; i++)
    if(vecini[i].size() % 2 || vecini[i].empty()) // daca graful contine un ciclu eulerian => graful este conex si toate nodurile au grad par
   {
       g << -1;
       return 0;
   }

   euler(1);

    for(int i = 0; i < de_afisat.size() - 1; i++)
        g << de_afisat[i] << " ";

    return 0;
}