Pagini recente » Rating Junc Raul Cosmin (DevilShadow) | Profil infoinblood | Cod sursa (job #758082)
Cod sursa(job #758082)
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
const int N_MAX=100011;
const int bSize=(1<<14)|1;
stack<int> S;
vector<int> r;
vector<int> G[N_MAX];
vector<int>::const_iterator it, iend;
int bIndex;
char buffer[bSize];
bool canHaveE(int N)
{
int i, count;
queue<int> Q;
bool was[N_MAX]={false};
for(i=1; i <= N; ++i)
if(G[i].size()&1)
return false;
was[1]=true;
for(Q.push(1), count=N-1; !Q.empty(); Q.pop())
{
i=Q.front();
for(it=G[i].begin(), iend=G[i].end(); it < iend; ++it)
if(false == was[*it])
{
--count;
if(0 == count)
return true;
was[*it]=true;
Q.push(*it);
}
}
return false;
}
void Euler(int x)
{
int y;
while(!G[x].empty())
{
y=G[x].back();
G[x].pop_back();
G[y].erase(find(G[y].begin(), G[y].end(), x));
S.push( x );
x=y;
}
}
void Read(istream& in, int& x)
{
if(-1 == bIndex)
{
in.read(buffer, bSize);
bIndex=0;
}
while(buffer[bIndex] < '0' || buffer[bIndex] > '9')
if(++bIndex == bSize)
{
in.read(buffer, bSize);
bIndex=0;
}
for(x=0; buffer[bIndex] >= '0' && buffer[bIndex] <= '9'; )
{
x=x*10+buffer[bIndex]-'0';
if(++bIndex == bSize)
{
in.read(buffer, bSize);
bIndex=0;
}
}
}
int main()
{
int N, M, x, y;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
for(Read(in, N), Read(in, M); M; --M)
{
Read(in, x); Read(in, y);
G[x].push_back(y);
G[y].push_back(x);
}
if(!canHaveE(N))
{
out<<"-1\n";
return EXIT_SUCCESS;
}
x=1;
do {
Euler(x);
r.push_back(x=S.top()); S.pop();
}while(!S.empty());
copy(r.rbegin(), r.rend(), ostream_iterator<int>(out, " "));
out<<'\n';
return EXIT_SUCCESS;
}