Cod sursa(job #2172980)

Utilizator futurengineerOana Rosca futurengineer Data 15 martie 2018 19:29:21
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

using namespace std;

struct muchie {
  int x, y;
};

vector<int>mv[100001], st;
muchie m[500001];
int noduri, muchii, x, y;
bool viz[500001];

int main () {
  ifstream fi("ciclueuler.in");
  ofstream fo("ciclueuler.out");
  fi >> noduri >> muchii;
  for (int i = 1; i <= muchii; i++) {
    fi >> x >> y;
    mv[x].push_back(i);
    mv[y].push_back(i);
    m[i].x = x, m[i].y = y;
  }
  for (int i = 1; i <= noduri; i++)
    if (mv[i].size() & 1) {
      fo << -1; return 0;
    }
  st.push_back(1);
  while (!st.empty()) {
    int nc = st.back();
    if (!mv[nc].size())
      fo << nc << ' ', st.pop_back();
    else {
      int mc = mv[nc].back();
      mv[nc].pop_back();
      if (!viz[mc]) {
        viz[mc] = 1;
        if (m[mc].x == nc)
          st.push_back(m[mc].y);
        else
          st.push_back(m[mc].x);
      }
    }
  }
  return 0;
}