Cod sursa(job #3168191)

Utilizator PetraPetra Hedesiu Petra Data 11 noiembrie 2023 18:33:03
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

vector<int> G[100001];
stack<int> s;
int n, m;

int are_ciclueuler ()
{
    for (int i = 0; i < n; i++)
    {
        if (G[i].size() % 2 == 1) return 0;
    }
    return 1;
}
void euler(int v)
{
    while (G[v].size())
    {
        int w = G[v][0];
        G[w].erase(find(G[w].begin(), G[w].end(), v));
        G[v].erase(find(G[v].begin(), G[v].end(), w));
//        G[v][0] = G[v][G[v].size()-1];
//        G[v].pop_back();
        euler(w);
    }
    s.push(v);
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m ; i++)
    {
        int u, v;
        fin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if (!are_ciclueuler())
    {
        fout << -1;
        return 0;
    }
    euler(1);
    s.pop();
    while(!s.empty())
    {
        fout << s.top() << " ";
        s.pop();
    }
    return 0;
}