Cod sursa(job #2338589)

Utilizator ianiIani Biro iani Data 7 februarie 2019 17:14:40
Problema Ciclu Eulerian Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 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,*invers;
}*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;
        i->invers->sters=true;
        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* nou1=new nod;
        nou1->dest=y;
        nou1->next=noduri[x];
        nou1->sters=false;
        noduri[x]=nou1;
        nod* nou2=new nod;
        nou2->dest=x;
        nou2->next=noduri[y];
        nou2->sters=false;
        noduri[y]=nou2;
        nou1->invers=nou2;
        nou2->invers=nou1;
    }
    euler(1);
    if (ciclu.front()!=ciclu.back())
        fout<<"-1";
    else
        for (it=ciclu.end()-1;it!=ciclu.begin();it--)
            fout<<*it<<' ';
    return 0;
}