Pagini recente » Cod sursa (job #988301) | Cod sursa (job #1271913) | Cod sursa (job #81210) | Cod sursa (job #2776027) | Cod sursa (job #495815)
Cod sursa(job #495815)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
int c[100002],ce[500002],viz[100002],p = 1, u = 1, nr;
vector<int> a[100002];
void ciclu(int x)
{
nr = 1;
c[1] = x;
bool ok = true;
do
{
for (int i = 0; (size_t) i < a[x].size() && ok; i++)
{ int z = a[x][i];
if (a[x][i] !=c[1])
{
nr++;
c[nr] = a[x][i];
x = z;
break;
}
else
{ ok = false;
c[++nr] = c[1];
}
vector<int>::iterator j = find(a[z].begin(), a[z].end(), x);
a[z].erase(j);
a[x].erase(a[x].begin());
}
} while (ok);
}
void inser()
{
for (int i = u; i >= p + 1; i--)
ce[i + nr -1] = ce[i];
for (int i = 2; i <= nr; i++)
ce[p + i - 1] = c[i];
}
int main()
{
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int N, M;
in >> N >> M;
for (int i = 1; i <= M; i++)
{ int x, y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= N; i++)
if (a[i].size() % 2 !=0 || (viz[i] == 0 && a[i].size() != 0))
{ out << -1;
return 0;
}
ce[1] = 1;
while (p <= u)
{
if (a[ce[p]].size())
{
ciclu(ce[p]);
inser();
u += nr - 1;
}
else
p++;
}
for (int i = 1; i <= u-1; i++)
out << ce[i] << ' ';
}