Cod sursa(job #2566789)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 3 martie 2020 12:39:43
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

#define MAXN    100005
#define MAXM    500005

int N, M;
std::vector <std::pair <int, int>> ADC[MAXN];
inline void addEdge(int u, int v, int idx) {
    ADC[u].push_back({v, idx});
    ADC[v].push_back({u, idx});
}

bool seen[MAXM];
int rem[MAXN];
std::vector <int> oilar;
void DFS(int u = 1) {
    while (rem[u] < ADC[u].size()) {
        auto &it = ADC[u][rem[u]++];
        int v = it.first;
        int idx = it.second;
        if (seen[idx]) continue;
        seen[idx] = true;
        DFS(v);
    }   oilar.push_back(u);
}

#define FILENAME    std::string("ciclueuler")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int main()
{
    input >> N >> M;
    for (int i=0, u, v; i<M; ++i) input >> u >> v, addEdge(u, v, i);

    bool bNaspa = false;
    for (int i=1; i<=N; ++i)
        if (ADC[i].size()%2 == 1)
            bNaspa = true;

    if (bNaspa) output << -1;
    else {
        DFS();
        oilar.pop_back();
        for (auto &it:oilar) output << it << ' ' ;
    }

    return 0;
}