Cod sursa(job #2928485)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 23 octombrie 2022 00:13:59
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
// Mihai Priboi

#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

#define MAXN 100000
#define MAXM 500000

struct Edge {
  int x, y;

  int to(int from) {
    if(x == -1)
      return -1;
    if(from == x)
      return y;
    return x;
  }

  void del() {
    x = y = -1;
  }
};

int n, m;

vector<int> graph[MAXN + 1];
Edge edge[MAXM];

stack<int> cycle, sol;

int main() {
  FILE *fin, *fout;
  int i, x, y, node, e, neighbour;
  bool cycleFound;
  fin = fopen("ciclueuler.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &x, &y);
    graph[x].push_back(i);
    graph[y].push_back(i);
    edge[i] = {x, y};
  }

  fclose(fin);
  fout = fopen("ciclueuler.out", "w");

  for(i = 1; i <= n; i++) {
    if(graph[i].size() % 2) {
      fprintf(fout, "-1");
      return 0;
    }
  }

  cycle.push(1);
  while(!cycle.empty()) {
    node = cycle.top();

    if(!graph[node].empty()) {
      e = graph[node].back();
      graph[node].pop_back();
      
      neighbour = edge[e].to(node);
      if(neighbour != -1) {
        edge[e].del();
        cycle.push(neighbour);
      }
    } 
    else {
      sol.push(node);
      cycle.pop();
    }
  }
  sol.pop();

  while(!sol.empty()) {
    fprintf(fout, "%d ", sol.top());
    sol.pop();
  }

  fclose(fout);
  return 0;
}