Pagini recente » Cod sursa (job #1825741) | Cod sursa (job #1107742) | Cod sursa (job #2239517) | Cod sursa (job #410803) | Cod sursa (job #1204676)
using namespace std;
#include <fstream>
#include <vector>
#include <stack>
ofstream fout("ciclueuler.out");
const int Nmax = 100000;
int m, n;
vector<int> v[Nmax+1];
vector<int> sol;
int deg[Nmax+1];
bool uz[Nmax+1];
stack<int> S;
void read() ;
int DFS(int) ;
int esteEulerian() ;
void creareLant(int) ;
int main()
{
read();
if( !esteEulerian() ) {fout << "-1\n"; return 0;}
S.push(1);
while( !S.empty() )
{
creareLant(S.top());
sol.push_back(S.top());
S.pop();
}
vector<int>::iterator it = sol.begin(); ++it;
for(; it != sol.end(); ++it)
fout << *it << ' ';
fout << '\n';
return 0;
}
void read()
{
ifstream fin("ciclueuler.in");
int a, b;
fin >> n >> m;
for(; m; --m)
{
fin >> a >> b;
++deg[a]; ++deg[b];
v[a].push_back(b);
v[b].push_back(a);
}
fin.close();
}
int DFS(int vf)
{
int nr = 1, ok; uz[vf] = 1;
vector<int>::iterator it;
for(S.push(vf); !S.empty(); )
{
vf = S.top(); ok = 0;
for(it = v[vf].begin(); it != v[vf].end() && !ok; ++it)
if(!uz[*it])
{
S.push(*it);
uz[*it] = 1; ok = 1; ++nr;
}
if(!ok) S.pop();
}
return nr == n;
}
int esteEulerian()
{
if(!DFS(1)) return 0;
for(int i = 1; i <= n; ++i)
if(deg[i] & 1) return 0;
return 1;
}
void creareLant(int vf)
{
int nod;
vector<int>::iterator it;
while(deg[vf])
{
nod = *(v[vf].begin());
S.push(nod);
v[vf].erase(v[vf].begin());
for(it = v[nod].begin(); *it != vf; ++it) ;v[nod].erase(it);
--deg[vf]; --deg[nod];
vf = nod;
}
}