Cod sursa(job #804233)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 29 octombrie 2012 13:26:21
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

const int N = 100005;
const int M = 500005;

int n, m;
int dgr[N];
bool viz[N];
pair <int, int> edges[M];
vector <int> graph[N];
vector <int>::iterator it[M];
vector <int> sol;

void read() {
    f >> n >> m;

    for (int i = 1; i <= m; ++i) {
        f >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(i);
        graph[edges[i].second].push_back(i);
    }
}

bool noSol() {
    for (int i = 1; i <= m; ++i) {
        ++dgr[edges[i].first];
        ++dgr[edges[i].second];
    }

    for (int i = 1; i <= n; ++i)
        if (dgr[i] & 1)
            return true;

    return false;
}

void init() {
    for (int i = 1; i <= n; ++i)
        it[i] = graph[i].begin();
}

void dfs(int node) {
    while (it[node] != graph[node].end()) {
        if (viz[*it[node]]) {
            ++it[node];
            continue;
        }

        viz[*it[node]] = true;

        int nbr = edges[*it[node]].first + edges[*it[node]].second - node;
        ++it[node];
        dfs(nbr);
    }

    sol.push_back(node);
}

void print() {
    FORIT(it, sol)
        g << *it << ' ';
}

int main() {
    read();

    if (noSol()) {
        g << "-1\n";
        return 0;
    }
    
    init();
    dfs(1);
    print();
}