Pagini recente » Cod sursa (job #1606148) | Cod sursa (job #1800534) | Cod sursa (job #1447210) | Cod sursa (job #1266895) | Cod sursa (job #716518)
Cod sursa(job #716518)
#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
#define Nmax 100001
#define Mmax 500001
using namespace std;
int N,M,st[Nmax],gr[Nmax];
queue<int> Q;
vector< pair<int,int> > G[Nmax];
bitset<Mmax> viz;
void read()
{
FILE*f = fopen("ciclueuler.in","r");
fscanf(f,"%d%d",&N,&M);
int i,x,y;
for(i=1;i<=M;++i)
{
fscanf(f,"%d%d",&x,&y);
G[x].push_back(make_pair(y,i));
G[y].push_back(make_pair(x,i));
++gr[x];
++gr[y];
}
fclose(f);
}
void df(int x)
{
viz[x] = true;
for(vector< pair<int,int> >::iterator it = G[x].begin();it!=G[x].end();++it)
if(viz[it->first] == false)
df(it->first);
}
void euler()
{
st[++st[0]] = 1;
viz.reset();
int nod,vec,ind;
while(st[0])
{
nod = st[st[0]];
if(G[nod].size() == 0)
{
Q.push(nod);
--st[0];
continue;
}
vec = (G[nod].end()-1)->first;
ind = (G[nod].end()-1)->second;
G[nod].pop_back();
if(viz[ind] == false)
{
viz[ind] = true;
st[++st[0]] = vec;
}
}
}
int main()
{
read();
df(1);
int ok = 1;
for(int i=1;i<=N;++i)
if(viz[i] == false || gr[i] % 2 == 1)
ok = 0;
FILE*g = fopen("ciclueuler.out","w");
if(ok)
{
euler();
for(int i=1, ok = Q.size();i<ok;++i,Q.pop())
fprintf(g,"%d ",Q.front());
}
else
fprintf(g,"-1");
fclose(g);
return 0;
}