Pagini recente » Cod sursa (job #1547202) | Cod sursa (job #2171254) | Cod sursa (job #3154729) | Cod sursa (job #1661727) | Cod sursa (job #493861)
Cod sursa(job #493861)
#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 , v;
for ( Q.push(1) , seen[1] = true ; !Q.empty() ; ) {
v = Q.front(); Q.pop();
seen[v] = true;
for( typeof(G[v].begin()) it = G[v].begin() ; it != G[v].end() ; ++it )
if ( !seen[*it] ) Q.push(*it);
}
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 true;
}
void delete_edge(int v, int w) {
G[v].pop_back();
for( typeof(G[w].begin()) it = G[w].begin(); it != G[w].end() ; ++it)
if ( *it == v ) {
G[w].erase(it);
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;
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;
}