Pagini recente » Cod sursa (job #2987987) | Cod sursa (job #1033352) | Cod sursa (job #1115717) | Cod sursa (job #2256075) | Cod sursa (job #1060842)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=100005;
const int MAXM=500005;
int n,m;
int grad[MAXN];
vector<int> adj[MAXN],e;
stack<int> s;
bool is_eulerian()
{
for (int i=1; i<=n; ++i)
{
if (grad[i]%2)
return false;
}
return true;
}
void del_edge(int u,int v)
{
//delete edge from u
adj[u].pop_back();
//delete edge from v
for (vector<int>::iterator i=adj[v].begin(); i!=adj[v].end(); ++i)
{
if ((*i)==u)
{
adj[v].erase(i);
break;
}
}
}
void euler_cycle()
{
int u=0,v=0;
s.push(1);
while (!s.empty())
{
u=s.top();
if (!adj[u].empty())
{
v=adj[u].back();
s.push(v);
del_edge(u,v);
}
else
{
s.pop();
e.push_back(u);
}
}
}
int main()
{
int k,x,y;
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
scanf("%d%d",&n,&m);
for (k=1; k<=m; ++k)
{
scanf("%d%d",&x,&y);
++grad[x];
++grad[y];
adj[x].push_back(y);
adj[y].push_back(x);
}
if (is_eulerian())
{
euler_cycle();
for (vector<int>::iterator i=e.begin(); i!=e.end(); ++i)
printf("%d ",*i);
printf("\n");
}
else
{
printf("-1\n");
}
return 0;
}