Cod sursa(job #2343978)

Utilizator ianiIani Biro iani Data 14 februarie 2019 17:06:47
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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;
stack<int> stk;

/*
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;
        }
        i->sters=true;
        i->invers->sters=true;
        euler(i->dest);
    }
    //cout<<x<<' ';
    ciclu.push_back(x);
}*/

void euler()
{
    stk.push(1);
    while (!stk.empty())
    {
        int node=stk.top();
        nod* i=noduri[node];
        while (i!=NULL)
        {
            if (i->sters==true)
            {
                nod *aux=i;
                noduri[node]=i->next;
                delete aux;
            }
            i=i->next;
        }
        i=noduri[node];
        if (i!=NULL)
        {
            stk.push(i->dest);
            i->sters=true;
            i->invers->sters=true;
        }
        else
        {
            ciclu.push_back(node);
            stk.pop();
        }
    }
}

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();
    if (ciclu.front()!=ciclu.back())
        fout<<"-1";
    else
        for (it=ciclu.begin();it!=ciclu.end()-1;it++)
            fout<<*it<<' ';
    return 0;
}