Cod sursa(job #1638026)

Utilizator cautionPopescu Teodor caution Data 7 martie 2016 20:41:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <stack>
#include <list>
#include <vector>
#include <algorithm>

constexpr int kMaxN = 100000;

int n, m;
std::list<int> edges[kMaxN+1];
std::vector<int> eulerian_circuit;

bool isEulerian()
{
    for(int i = 1; i <= n; ++i)
        if(edges[i].size()%2 == 1 || edges[i].size() == 0) return false;
    return true;
}

void buildEulerianCircuit()
{
    std::stack<int> S;
    S.push(1);
    while(!S.empty()) {
        int x = S.top();
        if(edges[x].size() == 0) {
            eulerian_circuit.push_back(S.top());
            S.pop();
        }
        else {
            int y = edges[x].front();
            edges[x].pop_front();
            edges[y].erase(std::find(edges[y].begin(), edges[y].end(), x));
            S.push(y);
        }
    }
}

int main()
{
    std::ifstream in("ciclueuler.in");
    std::ofstream out("ciclueuler.out");
    in>>n>>m;
    for(int x, y, i = 1; i <= m; ++i) {
        in>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    if(isEulerian()) {
        buildEulerianCircuit();
        eulerian_circuit.pop_back();
        for(auto x : eulerian_circuit) out<<x<<' ';
    }
    else out<<"-1\n";
    return 0;
}