Pagini recente » Cod sursa (job #2563144) | Cod sursa (job #2682558) | Cod sursa (job #2211595) | Cod sursa (job #933031) | Cod sursa (job #920157)
Cod sursa(job #920157)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int MAX_N = 100100;
const int MAX_M = 500100;
int N, M;
pair<int, int> edges[MAX_M];
vector<int> graph[MAX_N];
bool visited[MAX_M];
int num_neighbours[MAX_N];
vector<int>::iterator iter[MAX_N];
void read_input();
bool is_eulerian();
void euler(int node);
int main() {
read_input();
if (is_eulerian()) {
euler(1);
} else {
fout << 0;
}
return 0;
}
void read_input() {
fin >> N >> M;
for (int i = 1; i <= M; ++i) {
fin >> edges[i].first >> edges[i].second;
graph[edges[i].first].push_back(i);
graph[edges[i].second].push_back(i);
}
}
bool is_eulerian() {
for (int i = 1; i <= N; ++i) {
if (graph[i].size() & 1) return false;
iter[i] = graph[i].begin();
}
return true;
}
inline int other_node(int edge, int node) {
return edges[edge].first + edges[edge].second - node;
}
void euler(int node) {
while (iter[node] != graph[node].end()) {
if (visited[*iter[node]] == true) {
++iter[node];
continue;
}
visited[*iter[node]] = true;
int neighbour = other_node(*iter[node], node);
++iter[node];
euler(neighbour);
}
fout << node << ' ';
}