Cod sursa(job #2633827)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 8 iulie 2020 19:20:00
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define f first
#define s second
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
struct nodS
{
    bool viz=false;
    vector<pair<int, int>> vecini;
};
int n,m,x,y,i,last;
bool fol[500005];
nodS nod[100005];
void euler(int poz)
{
    for(auto it : nod[poz].vecini)
    {
        if(!fol[it.s])
        {
            fol[it.s]=true;
            euler(it.f);
        }
    }

    if(last)
        fout<<last<<' ';
    last=poz;
}
void dfs(int poz)
{
    nod[poz].viz=true;
    for(auto it : nod[poz].vecini)
        if(!nod[it.f].viz)
            dfs(it.f);
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        nod[x].vecini.push_back({y, i});
        nod[y].vecini.push_back({x, i});
    }

    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);
    return 0;
}