Pagini recente » Cod sursa (job #937328) | Cod sursa (job #1183377) | Cod sursa (job #229630) | Cod sursa (job #1267699) | Cod sursa (job #1626654)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
struct Data {
int adj, edge;
Data *nxt;
Data() {
nxt = NULL;
}
Data(int adj, int edge) {
this->adj = adj;
this->edge = edge;
nxt = NULL;
}
};
class List {
public:
Data *p, *u;
List() {
p = u = NULL;
}
void push(int adj, int edge) {
if (p == NULL) {
p = new Data(adj, edge);
u = p;
return;
}
Data *aux = u;
u = new Data(adj, edge);
aux->nxt = u;
}
void pop(void) {
if (p == NULL)
return;
Data *aux = p->nxt;
delete p;
p = aux;
}
void makeCyclic(void) {
pop();
u->nxt = p;
}
} graph[100005], eulerCycle;
bool vis[100005], deleted[500005];
int deg[100005];
int entriesCount = 0;
void dfs(int node) {
vis[node] = true;
for (Data *it = graph[node].p; it != NULL; it = it->nxt) {
++entriesCount;
if (vis[it->adj])
continue;
dfs(it->adj);
}
}
void getEulerCycle(int node) {
while (graph[node].p != NULL) {
if (!deleted[graph[node].p->edge]) {
deleted[graph[node].p->edge] = true;
getEulerCycle(graph[node].p->adj);
}
graph[node].pop();
}
eulerCycle.push(node, 0);
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
graph[x].push(y, i);
graph[y].push(x, i);
deg[x]++, deg[y]++;
}
dfs(1);
for (int i = 1; i <= n; ++i) {
if (deg[i] & 1) {
fout << -1;
return 0;
}
}
if (entriesCount != 2 * m) {
fout << -1;
return 0;
}
getEulerCycle(1);
eulerCycle.makeCyclic();
for (Data *it = eulerCycle.p;;) {
fout << it->adj << ' ';
it = it->nxt;
if (it == eulerCycle.p)
break;
}
fout << '\n';
return 0;
}
//Trust me, I'm the Doctor!