Cod sursa(job #1552004)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 16 decembrie 2015 23:49:16
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

#define DIM 100010
using namespace std;

int node1, node2, node, ok;
int nrNodes, nrEdges, nextNode;
vector <int> Edges[DIM];
stack <int> Stack, Answer;

int main () {

    freopen ("ciclueuler.in" ,"r", stdin );
    freopen ("ciclueuler.out","w", stdout);

    scanf ("%d %d", &nrNodes, &nrEdges);

    for (int i = 1; i <= nrEdges; i ++) {
        scanf ("%d %d", &node1, &node2);

        Edges[node1].push_back(node2);
        Edges[node2].push_back(node1);
    }

    ok = 1;
    for (int i = 1; i <= nrNodes; i ++)
        if (Edges[i].size()%2)
            ok = 0;

    if (!ok)
        printf ("-1\n");
    else {

        Stack.push(1);

        while (!Stack.empty()) {
            node = Stack.top();

            if (Edges[node].size()) {
                nextNode = Edges[node].back();

                Stack.push(nextNode);
                Edges[node].pop_back();
                Edges[nextNode].erase( find(Edges[nextNode].begin(), Edges[nextNode].end(), node) );

            } else {
                node = Stack.top();

                Answer.push(node);
                Stack.pop();
            }
        }
    }

    while (Answer.size() != 1) {
        int node = Answer.top();

        printf ("%d ", node);
        Answer.pop();
    }

    return 0;
}