Pagini recente » Cod sursa (job #2922306) | Cod sursa (job #198759) | Cod sursa (job #2488138) | Cod sursa (job #2878618) | Cod sursa (job #697898)
Cod sursa(job #697898)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fi ("ciclueuler.in");
ofstream fo ("ciclueuler.out");
const int dimn = 100005, dimm = 500005;
int N, M, g[dimn], viz[dimm], R[dimm], S[dimn];
vector < pair <int, int> > V[dimn];
void cit ()
{
fi >> N >> M;
for (int i = 1, x, y; i <= M; i++)
{
fi >> x >> y;
V[x].push_back (make_pair (y, i));
V[y].push_back (make_pair (x, i));
g[x]++, g[y]++;
}
}
int verif1 ()
{
for (int i = 1; i <= N; i++)
if (g[i] & 1)
return 0;
return 1;
}
int verif2 ()
{
for (int i = 1; i <= M; i++)
if (!viz[i])
return 0;
return 1;
}
void euler ()
{
int n;
S[++S[0]] = 1;
while (S[0])
{
n = S[S[0]];
if ( V[n].empty() )
{
R[++R[0]] = S[S[0]--];
continue;
}
if (viz[ V[n].back().second ] == 0)
{
viz[ V[n].back().second ] = 1;
S[++S[0]] = V[n].back().first;
}
V[n].pop_back ();
}
}
void afi ()
{
for (int i = 1; i < R[0]; i++)
fo << R[i] << ' ';
}
int main ()
{
cit ();
if (!verif1 ())
{
fo << "-1 ";
return 0;
}
euler ();
if (!verif2 ())
{
fo << "-1 ";
return 0;
}
afi ();
return 0;
}