Cod sursa(job #2633821)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 8 iulie 2020 18:53:06
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
struct nodS
{
    bool viz=false;
    multiset<int> vecini;
};
int n,m,x,y,i;
vector <int> ans;
nodS nod[100005];
void euler(int poz)
{
    while(!nod[poz].vecini.empty())
    {
        int it=*nod[poz].vecini.begin();
        nod[poz].vecini.erase(nod[poz].vecini.begin());
        nod[it].vecini.erase(nod[it].vecini.find(poz));
        euler(it);
    }

    ans.push_back(poz);
}
void dfs(int poz)
{
    nod[poz].viz=true;
    for(int it : nod[poz].vecini)
        if(!nod[it].viz)
            dfs(it);
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod[x].vecini.insert(y);
        nod[y].vecini.insert(x);
    }

    for(i=1;i<=n;i++)
    {
        if(nod[i].vecini.size()%2)
        {
            fout<<-1;
            return 0;
        }
    }

    dfs(1);
    for(i=1;i<=n;i++)
        if(!nod[i].viz && !nod[i].vecini.empty())
        {
            fout<<-1;
            return 0;
        }

    euler(1);

    ans.pop_back();
    for(int it : ans)
        fout<<it<<' ';
    return 0;
}