Pagini recente » Cod sursa (job #1906964) | Cod sursa (job #2279054) | Cod sursa (job #1387545) | Cod sursa (job #828849) | Cod sursa (job #271614)
Cod sursa(job #271614)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define FIN "ciclueuler.in"
#define FOUT "ciclueuler.out"
#define N 100010
#define M 50010
using namespace std;
int n,m,nr,ok;
int * a[N];
int c[N], *poz[N];
void read()
{
int g[N]={0};
pair <int,int> v[M];
freopen(FIN, "r", stdin);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%d %d", &v[i].first, &v[i].second);
++g[v[i].first];
++g[v[i].second];
}
for (int i = 1; i <= n; ++i)
{
a[i] = new int[1+g[i]];
a[i][0] = 0;
poz[i] = new int[1+g[i]];
poz[i][0] = 0;
if (g[i] % 2)
{
printf("-1\n");
exit(0);
}
}
for (int i = 1; i <= m; ++i)
{
if(v[i].first == v[i].second)
{
a[ v[i].first ][ ++a[v[i].first][0]] = v[i].second;
poz[ v[i].first ][ ++poz[v[i].first][0]] = a[v[i].first][0];
continue;
}
a[ v[i].first ][ ++a[v[i].first ][0]] = v[i].second;
poz[ v[i].first ][ ++poz[v[i].first][0] ] = a[v[i].second][0] + 1;
a[ v[i].second ][ ++a[v[i].second ][0]] = v[i].first;
poz[ v[i].second ][ ++poz[v[i].second][0]] = a[v[i].first][0];
}
}
void solve(int x)
{
int i,y;
for (i = 1; i <= a[x][0]; ++i)
{
y = a[x][i];
if (y == -1)
continue;
a[x][i] = -1;
if(y!=x)
a[y][ poz[x][i] ] = -1;
solve(y);
}
c[ ++nr] = x;
}
void write()
{
freopen(FOUT, "w", stdout);
if (ok)
{
printf("-1\n");
return;
}
for (int i = 1; i < nr-1; ++i)
printf("%d ", c[i]);
printf("%d\n", c[nr-1]);
}
void write2()
{
freopen(FOUT, "w", stdout);
printf("a :\n");
for (int i = 1; i <= n; ++i)
{
printf("%d : ", i);
for (int j = 1; j <= a[i][0]; ++j)
printf("%d ", a[i][j]);
printf("\n");
}
printf("poz :\n");
for (int i = 1; i <= n; ++i)
{
printf("%d : ", i);
for (int j = 1; j <= poz[i][0]; ++j)
printf("%d ", poz[i][j]);
printf("\n");
}
fclose(stdout);
}
int main()
{
read();
//write2();
solve(1);
write();
}