Cod sursa(job #1330808)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 30 ianuarie 2015 23:16:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define Nmax 100100

using namespace std;

vector <int> Graph[Nmax], Answer;
stack <int> Stack;
int N;

void eraseEdge(int node, int neighbour) {
    Graph[node][0] = Graph[node][Graph[node].size() - 1];
    Graph[node].pop_back();
    Graph[neighbour].erase(find(Graph[neighbour].begin(), Graph[neighbour].end(), node));
}
void Solve() {

    int node;

    for(node = 1; node <= N; node++)
        if(Graph[node].size() & 1)
            return;

    Stack.push(1);

    while(!Stack.empty()) {

        node = Stack.top();

        if(Graph[node].size() == 0) {
            Answer.push_back(node);
            Stack.pop();
        }
        else {
            Stack.push(Graph[node][0]);
            eraseEdge(node, Graph[node][0]);
        }
    }

}
void Read() {

    int x, y, M;

    ifstream in("ciclueuler.in");
    in >> N >> M;

    while(M--) {
        in >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    in.close();
}
void Write() {

    ofstream out("ciclueuler.out");

    if(Answer.size() == 0)
        out << "-1";
    else
    for(int i = 0; i < Answer.size(); i++)
        out << Answer[i] << ' ';

    out << '\n';
    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}