Cod sursa(job #2740278)

Utilizator DragosC1Dragos DragosC1 Data 12 aprilie 2021 13:43:01
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
using namespace std;
 
int n, m, mch;
vector<pair<int, int>> a[100001];
bool vizitedmch[500001];
int rez;
vector<int> cicle;
 
void read() {
    int i, x, y;
    ifstream f("ciclueuler.in");
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        a[x].emplace_back(y, ++mch);
        a[y].emplace_back(x, mch);
    }
    f.close();
}
 
void dfs(int x) {
    pair<int, int> e;
    while (a[x].size() > 0) {
        e = a[x].back();
        a[x].pop_back();
        if (vizitedmch[e.second])
            continue;
        vizitedmch[e.second] = 1;
        dfs(e.first);
    }
    cicle.emplace_back(x);
}
 
void solve() {
    int i;
    for (i = 1; i <= n; i++)
        if (a[i].size() % 2 != 0) {
            rez = 1;
            break;
        }
    if (rez == 0) {
        dfs(1);
    }
}
 
void output() {
    ofstream g("ciclueuler.out");
    if (rez == 1)
        g << -1;
    else {
        for (int i = 0; i < cicle.size() - 1; i++)
            g << cicle[i] << ' ';
    }
    g.close();
}
 
int main() {
    read();
    solve();
    output();
    return 0;
}