Cod sursa(job #2815480)

Utilizator linte_robertLinte Robert linte_robert Data 9 decembrie 2021 18:41:29
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void euler( int v, vector < vector < int > > &lista_vecini, vector < int > &ciclu ){
    while( lista_vecini[v].size() != 0 ){
        int w = lista_vecini[v][ lista_vecini[v].size()-1 ];
        lista_vecini[v].pop_back();
 /*       for( int i = 0; i < lista_vecini[w].size(); i++ ){
            if( lista_vecini[w][i] == v ){
                lista_vecini[w][i] = lista_vecini[w][ lista_vecini[w].size()-1 ];
                lista_vecini[w].pop_back();
                break;
            }
        }*/
        euler(w, lista_vecini, ciclu);
    }
    ciclu.push_back(v);
}

int main(){
    ifstream fin("ciclueuler.in");
    ofstream fout("ciclueuler.out");
    int nr_noduri, nr_muchii;
    fin >> nr_noduri >> nr_muchii;

    vector < vector < int > > lista_vecini(nr_noduri+1);
    vector < int > ciclu;
    for( int i = 0; i < nr_muchii; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        lista_vecini[intrare].push_back(iesire);
        lista_vecini[iesire].push_back(intrare);
    }

    for( int i = 0; i < lista_vecini.size(); i++ ){
        if( lista_vecini[i].size() % 2 != 0 ){
            fout << -1;
            return 0;
        }
    }

    euler(1, lista_vecini, ciclu);

    for( int i = 0; i < ciclu.size()-1; i++ ){
        fout << ciclu[i] << " ";
    }
    return 0;
}