Cod sursa(job #2848397)

Utilizator ana_madalina_18Radu Ana Madalina ana_madalina_18 Data 12 februarie 2022 14:56:16
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m;
struct muchie
{
    int nod_urm;
    int ind_muchie;
};
vector <muchie> v[100009];
int vizitat[500009];
vector <int> rasp;
int urmatorul(int i)
{
    while(v[i].size() && vizitat[v[i].back().ind_muchie]==1)
    {
        v[i].pop_back();
    }
    if(v[i].size())
    {
        vizitat[v[i].back().ind_muchie]=1;
        return v[i].back().nod_urm;
    }
    return 0;
}
void drum_euler(int nod)
{
    rasp.push_back(nod);
    while(int x=urmatorul(nod))
    {
        drum_euler(x);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a, b;
        fin>>a>>b;
        muchie nou;
        nou.nod_urm=b;
        nou.ind_muchie=i;
        v[a].push_back(nou);

        nou.nod_urm=a;
        v[b].push_back(nou);
    }
    for(int i=1;i<=n;i++)
    {
        if(v[i].size()%2==1 || v[i].size()==0)
        {
            fout<<-1;
            return 0;
        }
    }
    drum_euler(1);
    for(int i=0;i<rasp.size()-1;i++)
    {
        fout<<rasp[i]<<' ';
    }
    return 0;
}