Pagini recente » Cod sursa (job #1945389) | Cod sursa (job #3146284) | Cod sursa (job #2311455) | Cod sursa (job #2343160) | Cod sursa (job #2345700)
#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;
}