Cod sursa(job #2376594)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 8 martie 2019 16:36:08
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <vector>
#include <fstream>

#define NMAX 100010
#define MMAX 500010

std::ifstream fin("ciclueuler.in");
std::ofstream fout("ciclueuler.out");

struct Edge {
    int node, id;
    Edge(int node, int id) {
        this->node = node;
        this->id = id;
    }
};

int n, m;
std::vector<Edge> ad[NMAX];

int len;
int cycle[NMAX];
bool vis[MMAX];

void euler(int node) {
    while (!ad[node].empty()) {
        Edge edge = ad[node].back();
        ad[node].pop_back();

        if (!vis[edge.id]) {
            vis[edge.id] = true;
            euler(edge.node);
        }
    }
    cycle[len++] = node;
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;

        ad[x].push_back(Edge(y, i));
        ad[y].push_back(Edge(x, i));
    }

    for (int i = 1; i <= n; i++)
        if (ad[i].size() & 1) {
            fout << "-1\n";
            return 0;
        }

    euler(1);
    for (int i = 1; i < len; i++)
        fout << cycle[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}