Cod sursa(job #2740276)

Utilizator DragosC1Dragos DragosC1 Data 12 aprilie 2021 13:24:20
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
using namespace std;

int n, m, mch;
vector<pair<int, int>> a[100001];
bool vizitedmch[500001];
int g[100001];
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);
        g[x]++, g[y]++;
    }
    f.close();
}

void dfs(int x) {
    int i;
    for (i = 0; i < a[x].size(); i++)
        if (!vizitedmch[a[x][i].second]) {
            vizitedmch[a[x][i].second] = 1;
            dfs(a[x][i].first);
        }
    cicle.emplace_back(x);
}

void solve() {
    int i;
    for (i = 1; i <= n; i++)
        if (g[i] % 2 != 0) {
            rez = 1;
            break;
        }
    if (rez == 0) {
        dfs(1);
    }
}

void output() {
    ofstream g("ciclueuler.out");
    if (rez == 1)
        g << -1;
    else {
        int i;
        for (i = 0; i < cicle.size() - 1; i++)
            g << cicle[i] << ' ';
    }
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}