Pagini recente » Cod sursa (job #1893897) | Cod sursa (job #2094745) | Cod sursa (job #1963665) | Cod sursa (job #1253123) | Cod sursa (job #1318357)
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
using namespace std ;
ifstream is("ciclueuler.in") ;
ofstream os("ciclueuler.out") ;
vector <bool> viz;
vector <int> answ, V[100010], g;
stack <int> S;
queue <int> Q;
int N, M ;
void Read() ;
void Solve() ;
void OUT() ;
void Solve(int x) ;
bool Ok() ;
void BFS() ;
int main()
{
vector<int> ::iterator it;
Read();
BFS();
if(!Ok())
os << -1;
else
{
int x = 1 ;
do {
Solve(x);
x = S.top();
S.pop();
answ.push_back(x);
}while( !S.empty() ) ;
for(it = answ.begin(); it!= answ.end(); ++it)
os << *it << ' ';
}
is.close() ;
os.close() ;
return 0 ;
}
void Read()
{
int x, y;
is >> N >> M;
g.resize(N+1);
viz.resize(N+1, true);
for(int i = 1; i <= M; ++i)
{
is >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
g[x]++, g[y]++;
}
}
void BFS()
{
vector<int> ::iterator it;
int nod;
viz[1] = true;
Q.push(1);
while(!Q.empty())
{
nod = Q.front();
Q.pop();
for(it = V[nod].begin(); it != V[nod].end(); ++it)
if(!viz[*it])
viz[*it] = true, Q.push(*it);
}
}
bool Ok()
{
for(int i = 1 ; i <= N ; ++ i)
if(!viz[i] || g[i]%2)
return false ;
return true ;
}
void Solve(int x)
{
vector<int> ::iterator it;
int y;
while(true)
{
if( V[x].empty() )
break ;
y = V[x][V[x].size()- 1];
S.push(x) ;
V[x].pop_back() ;
for(it = V[y].begin(); it != V[y].end(); ++it)
if(*it == x)
{
V[y].erase(it);
break ;
}
x = y;
}
}