Pagini recente » Cod sursa (job #476814) | Cod sursa (job #2946976) | Cod sursa (job #207469) | Cod sursa (job #1297965) | Cod sursa (job #431084)
Cod sursa(job #431084)
#include<fstream>
#include<vector>
#define nmax 100100
using namespace std;
vector <pair <int,int> > v[nmax];
int u[nmax],st[nmax],w[5*nmax],sol[nmax];
int n;
void dfs(int nod)
{
u[nod]=1;
vector<pair <int,int> >:: iterator fiu;
for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
if(!u[(*fiu).first])
dfs((*fiu).first);
}
int ok()
{
dfs(1);
for(int i=1;i<=n;i++)
if(!u[i])
return 0;
int zero=0,i;
for(i=1;i<=n&&!zero;i++)
if(v[i].size()%2)
zero=1;
return 1^zero;
}
int main()
{
int m,i,x,y,k=0,done;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
v[x].push_back(make_pair(y,i));
v[y].push_back(make_pair(x,i));
}
if(!ok())
{
g<<"-1";
return 0;
}
st[++k]=1;
while(k)
{
done=0;
while(!v[st[k]].empty()&&!done)
{
if(!w[v[st[k]].back().second])
{
st[k+1]=v[st[k]].back().first;
w[v[st[k]].back().second]=1;
done=1;
}
else
v[st[k]].pop_back();
}
if(done)
k++;
else
sol[++sol[0]]=st[k--];
}
for(i=1;i<sol[0];i++)
g<<sol[i]<<' ';
return 0;
}