Cod sursa(job #2875372)

Utilizator BorodiBorodi Bogdan Borodi Data 21 martie 2022 15:34:51
Problema Critice Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define Nmax 500001
#include <vector>
#include <stack>
#include <map>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n, m, x, y;
typedef vector <int> VI;
map < pair <int , int >, int> Edge;
int G[Nmax];
VI Ans, V[Nmax];

void DFS(int vertex){
    for(int new_vertex : V[vertex]){
        Edge[{vertex, new_vertex}]--;
        Edge[{new_vertex, vertex}]--;

        if(Edge[{ vertex, new_vertex }] >= 0){
            DFS(new_vertex);
            Ans.push_back(vertex);
        }
    }

}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
        Edge[{x, y}]++;
        Edge[{y, x}]++;
        G[x]++; G[y]++;
    }

    for(int i = 1; i <= n; ++i)
        if(G[i] % 2 == 1){
            fout << -1;
            return 0;
        }

    DFS(1);
    reverse(Ans.begin(), Ans.end());

    for(int i : Ans)
        fout << i << ' ';

    return 0;
}