Cod sursa(job #2345700)

Utilizator crion1999Anitei cristi crion1999 Data 16 februarie 2019 16:54:57
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 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];



int grad[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();

        if (noduri[node]!=NULL)

        {

            while (noduri[node]!=NULL&&noduri[node]->sters==true)

            {

                noduri[node]=noduri[node]->next;

            }

            if (noduri[node]!=NULL)

            {

                stk.push(noduri[node]->dest);

                noduri[node]->sters=true;

                noduri[node]->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;

        grad[x]++;

        grad[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;

    }

    for (int i=1;i<=n;i++)

        if(grad[i]%2==1)

        {

            fout<<-1;

            return 0;

        }

    euler();

    for (it=ciclu.begin();it!=ciclu.end()-1;it++)

        fout<<*it<<' ';

    return 0;

}