Pagini recente » Cod sursa (job #2415014) | Cod sursa (job #2815413) | Cod sursa (job #985252) | Cod sursa (job #1745430) | Cod sursa (job #633330)
Cod sursa(job #633330)
#include<cstdio>
#include<stack>
#include<queue>
#include<list>
using namespace std;
list<int> rez;
list<int> l[100004];
int viz[100005],deg[100004];
int n, m;
queue<int> q;
stack<int> s;
void bfs(int v)
{ q.push(v); viz[v]=1;
while(!q.empty())
{ int nod = q.front();
q.pop();
for(list<int>::iterator it = l[nod].begin(); it != l[nod].end(); it++)
if(viz[*it] == 0)
{ viz[*it] = 1;
q.push(*it);
}
}
}
int ver_euler()
{
bfs(1);
for(int i = 2; i <= n; i++)
if(viz[i] == 0)
return 0;
for(int i = 1; i <= n; i++)
if(deg[i] %2 == 1)
return 0;
return 1;
}
void euler(int nod)
{ while(!l[nod].empty())
{ int urm = l[nod].front();
s.push(nod);
l[nod].pop_front();
deg[nod]--;
deg[urm]--;
for(list<int>::iterator it = l[urm].begin(); it != l[urm].end(); it++)
if(*it == nod)
{ l[urm].erase(it);
break;
}
nod = urm;
}
}
int solve()
{ int var = ver_euler();
if(var == 0)
return -1;
do
{
euler(var);
var = s.top();
s.pop();
rez.push_back(var);
}while( !s.empty() );
return 1;
}
int main()
{ freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
scanf("%d%d", &n, &m);
int x, y;
for(int i = 1; i <= m; i++ )
{
scanf("%d%d", &x, &y);
l[x].push_back(y);
l[y].push_back(x);
deg[x]++;
deg[y]++;
}
if (solve() == -1) printf("-1");
else
for(list<int>::iterator it = rez.begin(); it != rez.end(); it++)
printf("%d ",*it);
return 0;
}