Pagini recente » Cod sursa (job #1264580) | Cod sursa (job #1167974) | Cod sursa (job #1130053) | Cod sursa (job #2156832) | Cod sursa (job #971679)
Cod sursa(job #971679)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
const int MAX_N(100001);
int n, m;
std::deque<int> Graph [MAX_N];
bool Ok;
bool Mark [MAX_N];
std::vector<int> Cycle;
std::stack<int> Stack;
inline void Read (void)
{
std::freopen("ciclueuler.in","r",stdin);
std::scanf("%d %d\n",&n,&m);
for (int i(0), a, b ; i < m ; ++i)
{
std::scanf("%d %d",&a,&b);
Graph[a].push_back(b);
Graph[b].push_back(a);
}
std::fclose(stdin);
}
inline void Print (void)
{
std::freopen("ciclueuler.out","w",stdout);
if (Ok)
{
for (int index(0) ; index < Cycle.size() ; ++index)
std::printf("%d ",Cycle[index]);
}
else
std::printf("-1");
std::putchar('\n');
std::fclose(stdout);
}
inline void BreadthFirstSearch (void)
{
std::queue<int> queue;
queue.push(1);
Mark[1] = true;
int i, j;
while (!queue.empty())
{
i = queue.front();
queue.pop();
for (j = 0 ; j < Graph[i].size() ; ++j)
if (!Mark[Graph[i][j]])
{
Mark[Graph[i][j]] = true;
queue.push(Graph[i][j]);
}
}
}
inline bool Valid (void)
{
BreadthFirstSearch();
for (int i(1) ; i <= n ; ++i)
if (!Mark[i] || Graph[i].size() % 2)
{
Ok = false;
return false;
}
Ok = true;
return true;
}
inline void DepthFirstSearch (int node)
{
int neighbor;
while (!Graph[node].empty())
{
Stack.push(node);
neighbor = Graph[node].front();
Graph[node].pop_front();
auto ptr(std::find(Graph[neighbor].begin(),Graph[neighbor].end(),node));
Graph[neighbor].erase(ptr);
node = neighbor;
}
}
inline void EulerCycle (void)
{
int node(1);
do
{
DepthFirstSearch(node);
node = Stack.top();
Stack.pop();
Cycle.push_back(node);
}
while (!Stack.empty());
}
int main (void)
{
Read();
if (Valid())
EulerCycle();
Print();
return 0;
}