Pagini recente » Cod sursa (job #2420220) | Cod sursa (job #2849683) | Cod sursa (job #1397688) | Cod sursa (job #1194993) | Cod sursa (job #1212189)
#include<iostream>
#include<cstdio>
#include<list>
#include<stack>
#include<vector>
using namespace std;
vector<int>g[100005];
vector<int> sol;
stack<int> s;
int n;
int gr[100005], viz[100005];
void DF(int v)
{
viz[v]=1;
for(int i=0; i<g[v].size(); i++)
{
if(viz[g[v][i]]==0)
DF(g[v][i]);
}
}
bool verific()
{
DF(1);
for(int i=1; i<=n; i++)
if(viz[i]==0)
return 0;
for(int i=1; i<=n; i++)
if(gr[i]%2==1)
return 0;
return 1;
}
void ciclu(int v)
{
int w;
while(!g[v].empty())
{
w=g[v].front();
s.push(v);
gr[v]--;
gr[w]--;
g[v].erase(g[v].begin());
for(vector<int>::iterator it=g[w].begin(); it!=g[w].end(); it++)
{
if(*it==v) {
g[w].erase(it);
break;
}
}
v=w;
}
}
int main()
{
FILE *fin, *fout;
fin=fopen("ciclueuler.in", "r");
fout=fopen("ciclueuler.out", "w");
int x, y, m;
fscanf(fin, "%d %d", &n, &m);
for(int i=0; i<m; i++)
{
fscanf(fin, "%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
gr[x]++;
gr[y]++;
}
if(verific()==0)
fprintf(fout, "-1");
else {
int v=1;
do{
ciclu(v);
v=s.top();
s.pop();
sol.push_back(v);
}while(!s.empty());
for(int i=0; i<sol.size(); i++)
{
fprintf(fout, "%d ", sol[i]);
}
}
}