Pagini recente » Cod sursa (job #1838291) | Cod sursa (job #2067835) | Cod sursa (job #2724831) | Cod sursa (job #904880) | Cod sursa (job #672088)
Cod sursa(job #672088)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <vector>
using namespace std;
#define maxSize 100002
int nodes;
vector<int> graph[maxSize];
vector<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) {
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;
}
// un fel de "graph[currentNode].pop_front();"
// cu liste primesc Killed by signal 11(SIGSEGV) si Killed by signal 6(SIGABRT)
neighbour = graph[currentNode].begin();
graph[currentNode].erase(neighbour);
euler(next);
}
nodeList.push_back(currentNode);
}
void write(bool status) {
ofstream out("ciclueuler.out");
vector<int>::iterator currentNode;
// nodul de inceput apare de doua ori
// (la inceput si la sfarsit)
nodeList.pop_back();
if(status)
for(currentNode=nodeList.begin();currentNode!=nodeList.end();currentNode++)
out << *currentNode << " ";
else
out << "-1";
out.close();
}