Pagini recente » Cod sursa (job #2678169) | Cod sursa (job #2776077) | Cod sursa (job #1249471) | Cod sursa (job #1253827) | Cod sursa (job #2686266)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
const int dim=1e5+10;
typedef long long ll;
typedef pair<int,int> pi;
int t,T,n,m,a,b,dx[dim];
struct edge
{
int mch,ord;
};
vector < edge > V[dim];
vector < int > A,viz(dim,0);
void BFS()
{
queue < int > qu;
qu.push(1);
viz[1]=1;
while(!qu.empty())
{
int nod=qu.front();
qu.pop();
viz[nod]=2;
for(edge x:V[nod])
if(!viz[x.mch])
{
viz[x.mch]=1;
qu.push(x.mch);
}
}
}
void Euler(int nod)
{
while(!V[nod].empty())
{
int vecin=V[nod].back().mch;
int idx=V[nod].back().ord;
V[nod].pop_back();
if(!viz[idx])
{
viz[idx]=1;
Euler(vecin);
}
}
A.pb(nod);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>a>>b;
V[a].pb({b,i});
V[b].pb({a,i});
dx[a]++;
dx[b]++;
}
BFS();
for(int i=1;i<=n;i++)
if(!viz[i] || dx[i]%2==1)
{
g<<-1;
return 0;
}
for(int i=1;i<=n;i++) viz[i]=0;
Euler(1);
reverse(A.begin(),A.end());
A.pop_back();
for(unsigned int x:A)
g<<x<<' ';
return 0;
}