Cod sursa(job #2290024)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 25 noiembrie 2018 17:50:19
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100005;
const int MMAX = 500005;

int N, M;

vector<int> G[NMAX];
vector<bool> usedEdge(MMAX, false);

stack<int> st;

int from[MMAX];
int to[MMAX];


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

   iff >> N >> M;

   for (int i = 1; i <= M; ++i) {
      int x,y;
      iff >> x >> y;
      G[x].push_back(i);
      G[y].push_back(i);
      from[i] = x;
      to[i]   = y;
   }

   for (int i = 1; i <= N; ++i) {
      if (int(G[i].size()) & 1) {
         off << "-1";
         return 0;
      }
   }

   st.push(1);
   vector<int> ans;
   while (!st.empty()) {
      int top = st.top();

      if (!G[top].empty()) {
         int e = G[top].back();
         G[top].pop_back();
         if (!usedEdge[e]) {
            usedEdge[e] = true;
            int v = from[e] ^ to[e] ^ top;
            st.push(v);
         }
      } else {
         st.pop();
         ans.push_back(top);
      }
   }

   for (int i = 0; i < int(ans.size()) - 1; ++i) {
      off << ans[i] << " ";
   }

   return 0;
}