Pagini recente » Cod sursa (job #2377558) | Cod sursa (job #2353696) | Cod sursa (job #3002100) | Cod sursa (job #2781121) | Cod sursa (job #718683)
Cod sursa(job #718683)
#include <stdio.h>
#include <stack>
#include <queue>
#include <list>
#define nn 100010
using namespace std;
list <int> G[nn];
list <int> L;
stack <int> S;
int n, m, grad[nn], viz[nn];
void citire(){
scanf("%d %d",&n, &m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
grad[x]++; grad[y]++;
}
}
void visit(int x) {
for( typeof(G[x].begin()) it = G[x].begin() ; it != G[x].end() ; ++it )
if( !viz[*it] )
{
viz[*it] = 1;
visit(*it);
}
}
int check_eulerian(){
visit(1);
for( int i=1;i<=n;++i )
if( !viz[i] || grad[i]%2==1 )
return 0;
return 1;
}
void sterg(int x, int y){
G[x].pop_front();
grad[x]--; grad[y]--;
for( typeof(G[y].begin()) it = G[y].begin() ; it != G[y].end() ; ++it )
if( *it == x )
{
G[y].erase(it);
return;
}
}
void eulerian( int nod ){
int next;
while( ! G[nod].empty() )
{
next = G[nod].front();
S.push(nod);
sterg(nod, next);
nod = next;
}
}
void solve()
{
int ok = check_eulerian();
if(ok)
{
int x = 1;
do
{
eulerian(x);
x = S.top();
S.pop();
L.push_front(x);
} while( !S.empty() );
for( typeof(L.begin()) it = L.begin() ; it != L.end() ; ++it )
printf("%d " ,*it);
}
else
printf("-1");
}
int main()
{
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
citire();
solve();
return 0;
}