Pagini recente » Cod sursa (job #39288) | Cod sursa (job #1911702) | Cod sursa (job #1235118) | Cod sursa (job #1141029) | Cod sursa (job #1064982)
#include <fstream>
#include <list>
#include <queue>
#include <stack>
class Graph {
public:
struct Vertex {
std::list<int> myL;
Vertex() : myL(std::list<int>()) {
}
};
int nV;
Vertex *myArr;
~Graph() {
nV = 0;
delete[] myArr;
}
Graph(int a) : nV(a) {
myArr = new Vertex[nV + 1];
for(int i = 1; i <= nV; i++) {
myArr[i] = Vertex();
}
}
bool eulerian() {
for(int i = 1; i <= nV; i++) {
if((int)myArr[i].myL.size() & 1) {
return false;
}
}
std::queue<int> myQ;
char *myB = new char[nV + 1];
for(int i = 1; i <= nV; i++) {
myB[i] = 0;
}
myQ.push(1);
myB[1] = 1;
while(!myQ.empty()) {
int i = myQ.front();
myQ.pop();
for(auto it = myArr[i].myL.begin(); it != myArr[i].myL.end(); it++) {
if(myB[*it] == 0) {
myQ.push(*it);
myB[*it] = 1;
}
}
}
bool ok = true;
for(int i = 1; i <= nV; i++) {
if(myB[i] == 0) {
ok = false;
break;
}
}
delete[] myB;
return ok;
}
void pushEdge(int a, int b) {
myArr[a].myL.push_back(b);
myArr[b].myL.push_back(a);
}
std::list<int> solve() {
std::list<int> sol;
std::stack<int> myS;
int x = 1;
do{
while(!myArr[x].myL.empty()) {
int y = myArr[x].myL.front();
myArr[x].myL.pop_front();
myS.push(x);
std::list<int>::iterator it;
for(auto it = myArr[y].myL.begin(); it != myArr[y].myL.end(); it++) {
if(*it == x) {
myArr[y].myL.erase(it);
break;
}
}
x = y;
}
x = myS.top();
myS.pop();
sol.push_back(x);
}while(!myS.empty());
return sol;
}
};
int main() {
std::ifstream in("ciclueuler.in");
std::ofstream out("ciclueuler.out");
int nV, nE;
in >> nV >> nE;
Graph a(nV);
for(int i = 0; i < nE; i++) {
int c, d;
in >> c >> d;
a.pushEdge(c, d);
}
if(!a.eulerian()) {
out << -1;
return 0;
}
std::list<int> mySol = a.solve();
for(auto it = mySol.begin(); it != mySol.end(); it++) {
out << *it << ' ';
}
return 0;
}