Pagini recente » Cod sursa (job #1121611) | Cod sursa (job #234238) | Cod sursa (job #2096608) | Cod sursa (job #854695) | Cod sursa (job #536221)
Cod sursa(job #536221)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
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;
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();
}