Pagini recente » Cod sursa (job #1848867) | Cod sursa (job #672295) | Cod sursa (job #2938235) | Cod sursa (job #642690) | Cod sursa (job #688569)
Cod sursa(job #688569)
#include <fstream>
#include <vector>
#include <cstdlib>
#define NMAX 100008
#define MMAX 500008
#define InFile "ciclueuler.in"
using namespace std;
ofstream fout("ciclueuler.out");
vector <int> G[NMAX];
int n, lgh,inc,sf,m,gr[NMAX],sol[NMAX],n_sol,n_stiva,stiva[MMAX];
struct mch {int a; int b;} muchie[MMAX];
bool vizitat[MMAX];
void Citire();
void Afisare();
void verificare();
void euler();
int main()
{
Citire();
verificare();
euler();
Afisare();
return 0;
}
void euler()
{
stiva[++n_stiva] = 1;
int nod; int mch_sel;
unsigned int i;
while (n_stiva > 0)
{
nod = stiva[n_stiva];
for (i = 0; i < G[nod].size(); ++i)
{
mch_sel = G[nod][i];
if (!vizitat[mch_sel])
{
vizitat[mch_sel] = true;
if (muchie[mch_sel].a == nod)
stiva[++n_stiva] = muchie[mch_sel].b;
else
stiva[++n_stiva] = muchie[mch_sel].a;
break;
}
}
if (i == G[nod].size())
{
sol[++n_sol] = nod;
--n_stiva;
}
}
}
void Citire()
{int i, x,y;
ifstream fin(InFile);
fin>>n>>m;
for (i=1; i<=m; i++)
{
fin>>x>>y;
G[x].push_back(i);
G[y].push_back(i);
gr[x]++; gr[y]++;
muchie[i].a=x; muchie[i].b=y;
vizitat[i]=false;
}
}
void verificare()
{
for (int i=1;i<=n;i++)
if (gr[i]%2)
{
fout<<"-1\n";
fout.close();
exit(0);
}
}
void Afisare()
{
for (int i = n_sol; i >= 2; --i)
fout<<sol[i]<<' ';
fout<<'\n';
fout.close();
}