Cod sursa(job #3201959)

Utilizator manudragoDragomir Manuel manudrago Data 10 februarie 2024 11:04:50
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int NMAX = 100001;

/// [nodul_vecin, idx_muchiei]
vector < pair < int, int > > G[NMAX];
int grad[NMAX];
int viz[5 * NMAX];
int N, M;

void read(){
    fin >> N >> M;
    for(int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        G[x].push_back({y, i});
        G[y].push_back({x, i});
        grad[x]++;
        grad[y]++;
    }
}

stack < int > ciclu;
void euler(int nod){
    for(pair < int, int > nbr: G[nod]){
        int nod_nbr = nbr.first;
        int idx_much = nbr.second;
        if(!viz[idx_much]){
            viz[idx_much] = 1;
            euler(nod_nbr);
        }
    }
    ciclu.push(nod);
}


int main()
{
    read();
    /// STEP 1 - checky check
    for(int i = 1; i <= N; i++){
        if(grad[i] % 2){
            fout << -1;
            return 0;
        }
    }

    /// STEP 2 - start graf euler
    euler(1);
    while(!ciclu.empty()){
        fout << ciclu.top() << " ";
        ciclu.pop();
    }
    return 0;
}