Pagini recente » Cod sursa (job #2156246) | Cod sursa (job #2961806) | Cod sursa (job #2829753) | Cod sursa (job #2368131) | Cod sursa (job #1609107)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define pb push_back
#define nrmax 100001
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n , m , x , y ;
vector < int > G[nrmax];
vector < int > sol;
int grad[nrmax];
bool used[nrmax];
void dfs ( int i )
{
used[i] = true;
for ( vector < int > ::iterator j = G[i].begin(); j != G[i].end() ; j++ )
if (!used[(*j)])
dfs((*j));
}
void citire ( )
{
f >> n >> m ;
for ( ; m-- ; )
{
f >> x >> y ;
G[x].push_back(y);
G[y].push_back(x);
grad[x]++;
grad[y]++;
}
}
void ciclu_euler ( )
{
int x , alfa;
stack < int > st;
st.push(1);
while(!st.empty())
{
x = st.top();
if ( !G[x].empty() )
{
alfa = G[x][0];
st.push(alfa);
G[x].erase(G[x].begin());
G[alfa].erase ( find ( G[alfa].begin() , G[alfa].end() , x )) ;
}
else
{
sol.push_back(x);
st.pop();
}
}
}
void rezolva()
{
dfs(1);
for (int i = 1 ; i <= n ; i++ )
if ( !used[i] or grad[i]%2 == 1 )
{
g << -1;
return;
}
ciclu_euler();
for ( int i = sol.size()-1 ; i > 0 ; i-- )
g << sol[i] << " " ;
}
int main()
{
citire();
rezolva();
return 0;
}