Cod sursa(job #2382528)

Utilizator SemetgTemes George Semetg Data 18 martie 2019 14:15:11
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

const string FILE_NAME = "ciclueuler";
const int N_MAX = 100005;

int N;
list<int> g[N_MAX];
list<int> sol;

void init() {
    ifstream in { FILE_NAME + ".in" };
    
    int m;
    in >> N >> m;
    
    while (m--) {
        int x, y;
        in >> x >> y;
        
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
}

void findCycle(int node) {
    while (!g[node].empty()) {
        int next = g[node].back();
        g[node].pop_back();
        g[next].erase(find(g[next].begin(), g[next].end(), node));
        
        findCycle(next);
    }
    
    sol.push_back(node);
}

bool eulerian() {
    for (int i = 1; i <= N; ++i)
        if (g[i].size() % 2 != 0)
            return false;
    
    return true;
}

void solve() {
    if (eulerian())
        findCycle(1);
}

void print() {
    ofstream out { FILE_NAME + ".out" };
    
    if (!sol.empty())
        for (const auto& node : sol)
            out << node << ' ';
    else
        out << -1;
}

int main() {
    init();
    solve();
    print();
}