Pagini recente » Diferente pentru utilizator/deneo intre reviziile 372 si 254 | Cod sursa (job #664025)
Cod sursa(job #664025)
#include <cstdio>
#include <vector>
using namespace std;
const int N_MAX = 100010;
const int M_MAX = 500010;
struct mch
{
int a,b;
};
int n,m;
mch muchie[M_MAX];
bool vizitat[M_MAX];
vector<int> muchie_nod[N_MAX];
int stiva[M_MAX]; int n_stiva;
int grad[N_MAX]={0};
int sol[M_MAX]; int n_sol=0;
void citeste()
{
int x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d",&x,&y);
muchie[i] = (mch){x,y};
muchie_nod[x].push_back(i);
++grad[x];
muchie_nod[y].push_back(i);
++grad[y];
vizitat[i] = false;
}
}
bool graf_eulerian()
{
for (int i = 1; i <= n; ++i)
if (grad[i] % 2 == 1)
return false;
return true;
}
void ciclu_eulerian()
{
stiva[++n_stiva] = 1;
int nod; int mch_sel;
unsigned int i;
while (n_stiva > 0)
{
nod = stiva[n_stiva];
for (i = 0; i < muchie_nod[nod].size(); ++i)
{
mch_sel = muchie_nod[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 == muchie_nod[nod].size())
{
sol[++n_sol] = nod;
--n_stiva;
}
}
}
void scrie()
{
for (int i = n_sol; i >= 2; --i)
printf("%d ",sol[i]);
}
int main()
{
citeste();
if (graf_eulerian())
{
ciclu_eulerian();
scrie();
}
else
printf("-1\n");
return 0;
}