Pagini recente » Istoria paginii utilizator/ionel2022 | Monitorul de evaluare | Monitorul de evaluare | Istoria paginii runda/sith_lords_contest/clasament | Cod sursa (job #702967)
Cod sursa(job #702967)
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
#define NMAX 100001
#define MMAX 500001
#define pb push_back
#define mp make_pair
#define nod first
#define ind second
int N, M, i, x, y, Nod;
int Begin[NMAX];
vector< pair< int, int > > MuchiiNod[NMAX];
stack< int > Stiva;
bool UsedM[MMAX], Gata;
int main()
{
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
scanf("%d%d", &N, &M );
for( i = 1; i <= M; ++i )
{
scanf("%d%d", &x, &y );
MuchiiNod[x].pb( mp( y, i ) );
MuchiiNod[y].pb( mp( x, i ) );
}
for( i = 1; i <= N; ++i )
if( MuchiiNod[i].size()&1 )
{
printf("-1\n");
return 0;
}
memset( UsedM, false, sizeof(UsedM) );
memset( Begin, 0, sizeof(Begin) );
for( Stiva.push( 1 ); !Stiva.empty(); )
{
Nod = Stiva.top();
Gata = true;
for( i = Begin[Nod]; i < MuchiiNod[Nod].size(); ++i )
if( !UsedM[ MuchiiNod[Nod][i].ind ] )
{
UsedM[ MuchiiNod[Nod][i].ind ] = true;
Begin[Nod] = i;
Gata = false;
Stiva.push( MuchiiNod[Nod][i].nod );
break;
}
if( Gata )
{
if( Stiva.top() != 1 )
printf("%d ", Stiva.top() );
Stiva.pop();
}
}
printf("1\n");
return 0;
}