Cod sursa(job #1552007)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 16 decembrie 2015 23:52:36
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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], Answer;
stack <int> Stack;

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_back(node);
                Stack.pop();
            }
        }
    }

    ok = 0;
    vector <int> :: iterator it;
    for (it = Answer.begin(); it != Answer.end(); it ++) {
        if (!ok) ok = 1;
        else printf ("%d ", *it);
    }

    return 0;
}