Pagini recente » Cod sursa (job #535569) | Cod sursa (job #1307150) | Cod sursa (job #2585566) | Cod sursa (job #1040960) | Cod sursa (job #493857)
Cod sursa(job #493857)
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
const int maxn = 100005;
using namespace std;
vector <int> G[maxn] , Sol;
stack <int> St;
queue <int> Q;
int i , n , m , a , b , dg[maxn];
bool seen[maxn];
bool BF() {
int i;
for ( Q.push(1) , seen[1] = true ; !Q.empty() ; ) {
int v = Q.front(); Q.pop();
seen[v] = true;
for( i = 0 ; i < G[v].size(); ++i )
if ( !seen[G[v][i]] ) Q.push(G[v][i]);
}
for( i = 1 ; i <= n ; ++i )
if ( !seen[i] ) return false;
return true;
}
bool ok() {
for ( int i = 1 ; i <= n ; ++i )
if ( dg[i] & 1 ) return false;
return BF();
}
void delete_edge(int v, int w) {
G[v].pop_back();
int i;
for( i = 0 ; i < G[w].size() ; ++i)
if ( G[w][i] == v ) {
G[w].erase( G[w].begin() + i);
return;
}
}
void euler(int v)
{
int w;
while ( true ) {
if ( G[v].empty() ) break;
w = G[v].back();
St.push(v);
delete_edge (v , w);
v = w;
}
}
void ECycle()
{
if ( !ok() ) {
printf("-1\n");
return;
}
int v = 1;
Sol.push_back(1);
do
{
euler(v);
v = St.top() , St.pop();
Sol.push_back(v);
} while (! St.empty());
for( i = 0 ; i < Sol.size() ; ++i)
printf("%d ",Sol[i]);
}
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",&a,&b);
G[a].push_back(b), dg[a]++;
G[b].push_back(a), dg[b]++;
}
ECycle();
return 0;
}