Cod sursa(job #3003101)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 15 martie 2023 14:37:57
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5+2;
int n,m;
vector<int> adj[nmax];
vector<int> ciclu;
bool esteEulerian = 1;

struct muchStr{
    int a,b;
    bool activ;
} muchii[5*nmax];

void euler(int nod)
{
    cout<<nod<<" ";
    while(adj[nod].size())
    {
        int much = adj[nod].back();
        adj[nod].pop_back();
        if(muchii[much].activ)
        {
            muchii[much].activ = 0;
            if(nod == muchii[much].b)
                euler(muchii[much].a);
            else euler(muchii[much].b);
        }
    }
    ciclu.push_back(nod);
}

int main()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b;
        fin>>a>>b;
        adj[a].push_back(i);
        adj[b].push_back(i);
        muchii[i].a = a;
        muchii[i].b = b;
        muchii[i].activ = 1;
    }
    for(int i=1; i<=n; i++)
    {
        if(adj[i].size() % 2)
        {
            esteEulerian = 0;
            break;
        }
    }
    if(!esteEulerian)
    {
        fout<<-1;
        return 0;
    }
    euler(1);
    for(int i=0; i<ciclu.size() - 1; i++)
    {
        fout<<ciclu[i]<<" ";
    }
    return 0;
}