Pagini recente » Cod sursa (job #3276609) | Cod sursa (job #3282163) | Cod sursa (job #3251780) | Cod sursa (job #532014)
Cod sursa(job #532014)
#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
struct Node {
Node* next;
int val;
bool used;
Node(int x) {
next = 0;
val = x;
used = false;
}
Node *simetric;
};
Node* lista[100001];
int solu[500000];
int stack[500000];
int num = 0;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
Node* bagaNod(int x, int y) {
Node* newNode = new Node(y);
newNode->next = lista[x];
lista[x] = newNode;
return newNode;
}
void find_euler_cycle() {
int top = 0;
stack[0] = 0;
while (top>=0) {
int cn = stack[top];
while (lista[cn] && lista[cn]->used) {
lista[cn] = lista[cn]->next;
}
if (lista[cn]) {
stack[++top] = lista[cn]->val;
// lista[cn]->used = true; useless
lista[cn]->simetric->used = true;
lista[cn] = lista[cn]->next;
} else {
top--;
solu[num++] = cn;
}
}
}
int main() {
memset(lista, 0, sizeof(lista));
int n, m;
fin >> n >> m;
for (int i=0; i < m; i++) {
int x, y;
fin >> x >> y;
--x; --y;
Node* nod1 = bagaNod(x, y);
Node* nod2 = bagaNod(y, x);
nod1->simetric = nod2;
nod2->simetric = nod1;
}
find_euler_cycle();
// cout << num << " " << m << endl;
if (num != m+1 || solu[num-1]!=0) {
fout << -1 << endl;
fout.close();
return 0;
}
for(int i=0; i<num-1; i++) {
fout << solu[i] + 1 << " ";
}
fout << endl;
fout.close();
return 0;
}