Cod sursa(job #2338585)

Utilizator ianiIani Biro iani Data 7 februarie 2019 17:07:08
Problema Ciclu Eulerian Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct nod
{
    int dest;
    bool sters=false;
    nod* next;
}*noduri[100005];

vector<int> ciclu;
vector<int>::iterator it;

/*
euler (nod v)
cat timp (v are vecini)
w = un vecin aleator al lui v
sterge_muchie (v, w)
euler (w)
sfarsit cat timp
adauga v la ciclu
*/

void euler(int x)
{
    nod* i=noduri[x];
    while (i!=NULL)
    {
        if (i->sters==true)
        {
            i=i->next;
            continue;
        }
        int vecin=i->dest;
        i->sters=true;
        nod *j=noduri[vecin];
        nod *aux=nullptr;
        while (j!=NULL)
        {
            if (j->dest==x&&j->sters==false)
            {
                j->sters=true;
                aux=j;
                break;
            }
            j=j->next;
        }
        euler(vecin);
    }
    //cout<<x<<' ';
    ciclu.insert(ciclu.begin(), x);
}

int main()
{
    int n,m;
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        nod* nou=new nod;
        nou->dest=y;
        nou->next=noduri[x];
        nou->sters=false;
        noduri[x]=nou;
        nou=new nod;
        nou->dest=x;
        nou->next=noduri[y];
        nou->sters=false;
        noduri[y]=nou;
    }
    euler(1);
    if (ciclu.front()!=ciclu.back())
        fout<<"-1";
    else
        for (it=ciclu.end()-1;it!=ciclu.begin();it--)
            fout<<*it<<' ';
    return 0;
}