Pagini recente » Cod sursa (job #1548290) | Cod sursa (job #2422240) | Cod sursa (job #1981530) | Cod sursa (job #943304) | Cod sursa (job #530062)
Cod sursa(job #530062)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <list>
using namespace std;
#define maxSize 100002
int nodes;
list<int> graph[maxSize];
list<int> nodeList;
void read();
bool eulerianCycle();
inline 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 edges,from,to;
in >> nodes >> edges;
for(int i=1;i<=edges;i++) {
in >> from >> to;
// graf neorientat
graph[from].push_back(to);
graph[to].push_back(from);
}
in.close();
}
// un multigraf este Eulerian (admite un ciclu Eulerian) daca si numai daca este conex si toate nodurile sale au grad par
bool eulerianCycle() {
for(int currentNode=1;currentNode<=nodes;currentNode++)
if(graph[currentNode].size() % 2)
return false;
return true;
}
inline 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();
}
nodeList.push_back(currentNode);
}
void write(bool status) {
ofstream out("ciclueuler.out");
list<int>::iterator currentNode;
nodeList.pop_front();
if(status)
for(currentNode=nodeList.begin();currentNode!=nodeList.end();currentNode++)
out << *currentNode << " ";
else
out << "-1";
out.close();
}