Pagini recente » Cod sursa (job #1694744) | Cod sursa (job #2364076) | Cod sursa (job #44614) | Cod sursa (job #2020814) | Cod sursa (job #1414066)
//Problem euler
#include <cassert>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
#define len(c) (int)(c).size()
#define pb push_back
#define mp make_pair
#define x first
#define y second
typedef vector<int> VI;
typedef pair<int, int> PII;
int N, M;
vector<VI> graph;
vector<PII> edges;
vector<VI::iterator> git;
vector<bool> vis;
VI sol;
int other(int n, int e) {
return edges[e].x + edges[e].y - n;
}
void euler(int node) {
while (git[node] != end(graph[node])) {
int edge = *git[node];
advance(git[node], 1);
if (!vis[edge]) {
vis[edge] = 1;
euler(other(node, edge));
}
}
sol.pb(node);
}
int main() {
fin >> N >> M;
graph.resize(N + 1);
git.resize(N + 1);
edges.resize(M);
for (int i = 0, a, b; i < M; i += 1) {
fin >> a >> b;
graph[a].pb(i);
graph[b].pb(i);
edges[i] = mp(a, b);
}
vis.resize(len(edges));
for (int i = 1; i <= N; i += 1) {
if (len(graph[i]) & 1) {
fout << -1 << endl;
return 0;
}
git[i] = begin(graph[i]);
}
euler(1);
sol.pop_back();
for (auto v: sol) {
fout << v << ' ';
}
fout << endl;
return 0;
}