Pagini recente » Istoria paginii utilizator/seby97 | Istoria paginii utilizator/cristi.dana | Monitorul de evaluare | Istoria paginii utilizator/floppybestial | Cod sursa (job #697946)
Cod sursa(job #697946)
#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[dimm];
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, v, m;
S[++S[0]] = 1;
while (S[0])
{
n = S[S[0]];
if ( V[n].empty() )
{
R[++R[0]] = S[S[0]--];
continue;
}
v = V[n].back().first;
m = V[n].back().second;
V[n].pop_back ();
if (viz[m] == 0)
{
viz[m] = 1;
S[++S[0]] = v;
}
}
}
void afi ()
{
for (int i = 1; i < R[0]; i++)
fo << R[i] << '\n';
}
int main ()
{
cit ();
if (!verif1 ())
{
fo << "-1 ";
return 0;
}
euler ();
if (!verif2 ())
{
fo << "-1 ";
return 0;
}
afi ();
return 0;
}