Pagini recente » Cod sursa (job #1440174) | Cod sursa (job #410374) | Borderou de evaluare (job #2266406) | Cod sursa (job #620248) | Cod sursa (job #797753)
Cod sursa(job #797753)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
const int Nmax = 100010;
typedef vector<int>::iterator IT;
typedef list< pair<int,int> >::iterator LT;
vector<int> A[Nmax];
int Grad[Nmax],Marked[Nmax];
int N,M;
list< pair<int,int> > C, Sol;
ifstream F("ciclueuler.in");
ofstream G("ciclueuler.out");
void Get( int Nod )
{
Grad[Nod] = A[Nod].size();
Marked[Nod] = 1;
for ( IT it=A[Nod].begin();it!=A[Nod].end();++it )
if ( !Marked[ *it ] )
Get( *it );
}
int Ok()
{
for ( int i=1;i<=N;++i )
if ( A[i].size() && !Marked[i] )
return i;
return -1;
}
void Elimin( int a , int b )
{
for ( int i=0;i<int( A[a].size() );++i )
if ( A[a][i] == b )
{
swap( A[a][i] , A[a].back() );
A[a].pop_back();
}
for ( int i=0;i<int( A[b].size() );++i )
if ( A[b][i] == a )
{
swap( A[b][i] , A[b].back() );
A[b].pop_back();
}
}
int main()
{
F>>N>>M;
for ( int i=0,x,y;i<M;++i )
{
F>>x>>y;
A[x].push_back( y );
A[y].push_back( x );
}
Get( 1 );
for ( int i=1;i<=N;++i )
if ( Marked[i]==0 || Grad[i]&1 )
{
G<<"-1\n";
return 0;
}
Marked[1]=0;
for ( int Nod=Ok(),Last,Init; Nod != -1 ;Nod = Ok() )
{
Marked[Nod]=0;
Init = Nod;
Last = Nod;
Marked[Nod]=0;
Nod = A[Nod].back();
C.push_back( make_pair(Last,Nod) );
Elimin( Last,Nod );
while ( Nod != Init )
{
Marked[Nod]=0;
Last = Nod;
Nod = A[Nod].back();
C.push_back( make_pair(Last,Nod) );
Elimin( Last,Nod );
}
if ( Sol.empty() )
C.splice(Sol.begin(),C);
else
for ( LT it=Sol.begin();it!=Sol.end();++it)
if ( it->second == C.rbegin()->second )
{
C.splice(it,C);
break;
}
}
G<<Sol.begin()->first;
for ( LT it=Sol.begin();it!=Sol.end();++it)
G<<' '<<it->second;
G<<'\n';
return 0;
}