Cod sursa(job #1184084)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 11 mai 2014 10:42:51
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int knmax = 100005;

class edg{
public:
  int no, x, y, color;

  edg(){};

  edg(int n1, int a1, int a2){
    no = n1;
    x = a1;
    y = a2;
    color = 0;
  }

  int nbr(int x1){
    if(x == x1)
      return y;
    return x;
  }
};

vector<int> g[knmax];
vector<edg> t;

int evis[knmax * 5], nvis[knmax];
vector<int> ans;

void dfs(int x){
  nvis[x] = 1;
  for(int i = 0; i < g[x].size(); ++i)
    if(!evis[g[x][i]]){
      evis[g[x][i]] = 1;
      dfs(t[g[x][i]].nbr(x));
    }
  ans.push_back(x);
}

int main(){
  ifstream in("ciclueuler.in");
  ofstream out("ciclueuler.out");

  int n, m;
  in >> n >> m;

  for(int i = 1; i <= m; ++i){
    int x, y;
    in >> x >> y;
    t.push_back(edg(i, x, y));
    g[x].push_back(i - 1);
    g[y].push_back(i - 1);
  }

  dfs(1);

  if(ans.size() != m + 1)
    out << "-1";
  else
    for(int i = 0; i < ans.size(); ++i)
      out << ans[i] << " ";

  return 0;
}