Cod sursa(job #536227)

Utilizator feelshiftFeelshift feelshift Data 18 februarie 2011 13:35:49
Problema Ciclu Eulerian Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <vector>
#include <list>
using namespace std;

#define maxSize 100001

int nodes;
vector<int> graph[maxSize];
list<int> nodeList;

void read();
bool eulerianCycle();
inline void euler(int currendNode);
void write();

int main() {
    read();

    if(eulerianCycle())
        euler(1);

    write();

    return (0);
}

void read() {
    ifstream in("ciclueuler.in");
    int edges,from,to;

    in >> nodes >> edges;

    for(int i=1;i<=edges;i++) {
        in >> from >> to;

        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    in.close();
}

bool eulerianCycle() {
    for(int i=1;i<=nodes;i++)
        if(graph[i].size() % 2)
            return false;

    return true;
}

inline void euler(int currentNode) {
    int next;
    vector<int>::iterator neighbour;
    vector<int>::iterator neighbourOfNeighbour;

    neighbour = graph[currentNode].begin();

    while(graph[currentNode].size()) {
        neighbour = graph[currentNode].begin();
        next = *neighbour;

        for(neighbourOfNeighbour=graph[next].begin();neighbourOfNeighbour!=graph[next].end();++neighbourOfNeighbour)
            if(*neighbourOfNeighbour == currentNode) {
                graph[next].erase(neighbourOfNeighbour);
                break;
            }

        neighbour = graph[currentNode].begin();
        graph[currentNode].erase(neighbour);

        euler(next);
    }

    nodeList.push_back(currentNode);
}

void write() {
    ofstream out("ciclueuler.out");

    if(!nodeList.empty()) {
        nodeList.pop_front();

        list<int>::iterator it,end;
        end = nodeList.end();

        for(it=nodeList.begin();it!=end;++it)
            out << *it << " ";
    }
    else
        out << "-1";

    out.close();
}