Cod sursa(job #920157)

Utilizator toranagahVlad Badelita toranagah Data 20 martie 2013 09:01:00
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#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 << ' ';
}