Pagini recente » Cod sursa (job #46198) | Cod sursa (job #2059420) | Cod sursa (job #2829304) | Cod sursa (job #160251) | Cod sursa (job #2928485)
// Mihai Priboi
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define MAXN 100000
#define MAXM 500000
struct Edge {
int x, y;
int to(int from) {
if(x == -1)
return -1;
if(from == x)
return y;
return x;
}
void del() {
x = y = -1;
}
};
int n, m;
vector<int> graph[MAXN + 1];
Edge edge[MAXM];
stack<int> cycle, sol;
int main() {
FILE *fin, *fout;
int i, x, y, node, e, neighbour;
bool cycleFound;
fin = fopen("ciclueuler.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(i = 0; i < m; i++) {
fscanf(fin, "%d%d", &x, &y);
graph[x].push_back(i);
graph[y].push_back(i);
edge[i] = {x, y};
}
fclose(fin);
fout = fopen("ciclueuler.out", "w");
for(i = 1; i <= n; i++) {
if(graph[i].size() % 2) {
fprintf(fout, "-1");
return 0;
}
}
cycle.push(1);
while(!cycle.empty()) {
node = cycle.top();
if(!graph[node].empty()) {
e = graph[node].back();
graph[node].pop_back();
neighbour = edge[e].to(node);
if(neighbour != -1) {
edge[e].del();
cycle.push(neighbour);
}
}
else {
sol.push(node);
cycle.pop();
}
}
sol.pop();
while(!sol.empty()) {
fprintf(fout, "%d ", sol.top());
sol.pop();
}
fclose(fout);
return 0;
}