Cod sursa(job #3253473)

Utilizator StefanStratonStefan StefanStraton Data 2 noiembrie 2024 19:46:16
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[100001]; // v = vect care numara cate muchii au fost parcurse din fiecare nod
int sol[500001], cnt;
bool viz[500001];
vector <pair <int, int>> g[100001];


void ciclu_eulerian(int nod){
    while(v[nod] < g[nod].size()){
        if(!viz[g[nod][v[nod]].second]){ // daca muchia nu a fost parcursa
            viz[g[nod][v[nod]].second] = true;
            ciclu_eulerian(g[nod][v[nod]++].first);
        } else {
            v[nod]++; // daca muchia a fost parcursa incrementez v[nod]
        }
    }
    sol[++cnt] = nod;
}

int main() {
    int n, m;
    in >> n >> m;

    for(int i = 1; i <= m; i++){
        int nod1, nod2;
        in >> nod1 >> nod2;
        g[nod1].push_back(make_pair(nod2, i));
        g[nod2].push_back(make_pair(nod1, i));
    }

    bool ok = true;
    for(int i = 1; i <= n && ok; i++)
        if(g[i].size() % 2) ok = false;

    if(!ok) cout << -1;
    else {
        ciclu_eulerian(1); // dfs
        for(int i = 1; i < cnt; i++)
            cout << sol[i] << " ";
    }

    return 0;
}