Cod sursa(job #2757809)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 6 iunie 2021 16:05:17
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
#include <tuple>

using namespace std;
int N, M;
vector<vector<pair<int,int>>> Graph;
bitset<500005> used;


void euler(int k)
{
  stack<int> S;
  int v, index;
  do {
    while (Graph[k].size()) {
      tie(v, index) = Graph[k].back();
      Graph[k].pop_back();
      if (used[index]) continue;
      used[index] = true;
      S.push(k);
      k = v;
    }

    k = S.top();
    S.pop();
    printf("%d ", k + 1);
    
  } while (!S.empty());
}

int main()
{
  freopen("ciclueuler.in", "r", stdin);
  freopen("ciclueuler.out", "w", stdout);

  scanf("%d%d", &N, &M);
  Graph.resize(N);
  int x, y;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d", &x, &y);
    --x;
    --y;
    Graph[x].emplace_back(y, i);
    Graph[y].emplace_back(x, i);
  }

  for (auto it: Graph)
    if (it.size() % 2 == 1) {
      printf("-1\n");
      return 0;
    }

  euler(0);  
  
  return 0;
}