Pagini recente » Cod sursa (job #3139529) | Cod sursa (job #1735766) | Cod sursa (job #1626236) | Cod sursa (job #2298267) | Cod sursa (job #710541)
Cod sursa(job #710541)
#include <fstream>
#include <stack>
#include <queue>
#include <vector>
#define MAXN 100010
using namespace std;
bool done,viz[MAXN];
stack<int>S;
queue<int>Q;
vector<int> v[MAXN];
int deg[MAXN],m,n;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
void dfs(int x)
{
viz[x]=1;
for(int i=0;i<v[x].size();i++)
if(!viz[v[x][i]]) dfs(v[x][i]);
}
void sterge(int x,int y)
{
int i;
v[x].erase(v[x].begin());
for(i=0;i<v[y].size();i++) if(v[y][i]==x) break;
v[y].erase(v[y].begin()+i);
}
void euler(int x)
{
while(1)
{
if(v[x].size()==0) break;
int y=v[x][0];
S.push(x);
sterge(x,y);
x=y;
}
}
void solve(int x)
{
do
{
euler(x);
x=S.top(); S.pop();
Q.push(x);
} while(!S.empty());
while(!Q.empty())
{
fo<<Q.front()<<" ";
Q.pop();
}
}
int main()
{
int i,x,y;
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
deg[x]++; deg[y]++;
}
dfs(1);
for(i=1;i<=n;i++) if(deg[i]%2 or !viz[i]) done=1;
if(done) { fo<<"-1\n"; return 0; }
solve(1);
return 0;
}