Pagini recente » Cod sursa (job #257611) | Cod sursa (job #840363) | Cod sursa (job #623122) | Cod sursa (job #609576) | Cod sursa (job #515999)
Cod sursa(job #515999)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <list>
using namespace std;
int nodes,edges;
list<int> graph[100001];
list<int> solution;
void read();
bool eulerianCycle();
void euler(int currentNode);
void write(bool status);
int main() {
read();
if(eulerianCycle()) {
euler(1);
write(true);
}
else
write(false);
return (0);
}
void read() {
ifstream in("ciclueuler.in");
int 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;
}
void euler(int currentNode) {
list<int>::iterator firstIt,secondIt;
int next;
firstIt = graph[currentNode].begin();
while(firstIt != graph[currentNode].end()) {
next = *firstIt;
secondIt = graph[next].begin();
while(secondIt != graph[next].end()) {
if(*secondIt == currentNode) {
graph[next].erase(secondIt);
break;
}
secondIt++;
}
graph[currentNode].pop_front();
euler(next);
firstIt = graph[currentNode].begin();
}
solution.push_back(currentNode);
}
void write(bool status) {
ofstream out("ciclueuler.out");
list<int>::iterator it=solution.begin();
it++;
if(status)
for(;it!=solution.end();it++)
out << *it << " ";
else
out << "-1\n";
out.close();
}