Cod sursa(job #2837634)

Utilizator TiberiwTiberiu Amarie Tiberiw Data 22 ianuarie 2022 12:41:14
Problema Ciclu Eulerian Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define Dmax 100005

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m,grad[Dmax];

vector<int> G[Dmax],L;


void dfs(int nod)
{

    while(grad[nod])
    {
        int Vecin = G[nod][--grad[nod]];
        --grad[Vecin];
        vector<int>::iterator I;
        for(I = G[Vecin].begin() ; I < G[Vecin].end() ; I++)
                if(*I == nod)
                    G[Vecin].erase(I);



        dfs(Vecin);

    }
    L.push_back(nod);

}

bool ExistaEuler()
{
    for(int i = 1; i <= n; i++)
        if(grad[i]%2==1)
        return false;

    return true;
}

int main()
{
        f>>n>>m;
        for(int i = 1; i <= m; i++)
        {
            int x,y;
            f>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
            grad[x]++;
            grad[y]++;
        }


        if(!ExistaEuler())
            return -1;

        dfs(1);


        if(L.size() == m + 1)
        {
            for(unsigned int i = 0 ; i < L.size() - 1; i++)
                    g<<L[i]<<" ";
        }
        else
            return -1;




    return 0;
}