Pagini recente » Cod sursa (job #2553453) | Cod sursa (job #187884) | Cod sursa (job #821974) | Cod sursa (job #2359926) | Cod sursa (job #630304)
Cod sursa(job #630304)
#include <fstream>
#include <queue>
#include <list>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int NMAX = 100002;
int N , M , grad[NMAX];
bool viz[NMAX];
list<int> G[NMAX] , sol;
stack<int> S;
void read_data()
{
fin>>N>>M;
for(;M;M--)
{
int x , y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
grad[x]++ , grad[y]++;
}
}
void bfs(int v)
{
queue<int> Q;
Q.push(v) , viz[v] = 1;
while(!Q.empty())
{
v = Q.front() , Q.pop();
for(list<int>::const_iterator it=G[v].begin();it!=G[v].end();++it)
if(!viz[*it]) viz[*it] = 1 , Q.push(*it);
}
}
int eulerian()
{
bfs(1);
for(int i=1;i<=N;++i)
if(grad[i]%2 == 1 || !viz[i]) return 0;
return 1;
}
void sterge(int v,int w)
{
grad[v]--; grad[w]--;
G[v].pop_front();
for(list<int>::iterator it=G[w].begin();it!=G[w].end();++it)
if(*it==v)
{
G[w].erase(it);
break;
}
}
void euler(int v)
{
while(true)
{
if(G[v].empty()) break;
int w = G[v].front();
S.push(v);
sterge(v,w);
v = w;
}
}
void solve()
{
int v = eulerian();
if(v)
{
do {
euler(v);
sol.push_back( v = S.top() ), S.pop();
} while(!S.empty());
}
}
void print_out()
{
if(!sol.empty())
for(list<int>::const_iterator it=sol.begin();it!=sol.end();++it)
fout<<*it<<' ';
else
fout<<-1;
fout<<'\n';
}
int main()
{
read_data();
solve();
print_out();
return 0;
}