Cod sursa(job #1233840)

Utilizator sorynsooSorin Soo sorynsoo Data 26 septembrie 2014 09:42:15
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <list>
#include <stack>
using namespace std;
const int NMAX = 100005;

int N, M;
bool viz[NMAX];
list<int> G[NMAX];
stack<int> st;

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

void dfs(int node) {
    viz[node] = 1;
    for (int son =0; son<G[node].size(); son++)
        if (!viz[son])
            dfs(son);
}

void Euler(int node) {
    while (!G[node].empty()) {
        st.push(node);
        int nb = G[node].front();
        G[node].pop_front();
        list<int>::iterator it;
        for (it = G[nb].begin(); *it != node; ++it);
        G[nb].erase(it);
        node = nb;
    }
}

int main() {
    fin >> N >> M;
    while (M--) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    for (int i = 1; i <= N; ++i)
        if (!viz[i] || G[i].size() & 1) {
            fout << "-1\n";
            return 0;
        }

    int node = 1;
    do {
        Euler(node);
        node = st.top();
        st.pop();
        fout << node << " ";
    } while (!st.empty());
    return 0;
}