Cod sursa(job #915282)
#include <fstream>
#include <vector>
using namespace std;
void DepthFirstSearch(int vertex, vector<int> *&Graph, vector<int> &cycle)
{
int i, j;
for (i=0; i<Graph[vertex].size(); ++i)
{
int adjancted = Graph[vertex][i];
for (j=0; Graph[adjancted][j] != vertex; ++j);
Graph[adjancted][j] = Graph[adjancted][Graph[adjancted].size()-1];
Graph[adjancted].pop_back();
Graph[vertex][i] = Graph[vertex][Graph[vertex].size()-1];
Graph[vertex].pop_back();
--i;
if (Graph[adjancted].size())
{
cycle.push_back(adjancted);
cycle.push_back(vertex);
}
DepthFirstSearch(adjancted, Graph, cycle);
}
}
bool hasEdges(vector<int> *G, int N)
{
for (int i=1; i<=N; ++i)
if (G[i].size())
return 1;
return 0;
}
int main()
{
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int N, M, i, a, b;
vector<int> *Graph, cycle;
in>>N>>M;
Graph = new vector<int>[N+1];
for (i=0; i<M; ++i)
{
in>>a>>b;
Graph[a].push_back(b);
Graph[b].push_back(a);
}
DepthFirstSearch(1, Graph, cycle);
if (hasEdges(Graph, N))
{
out<<-1;
return 0;
}
vector<int>::iterator it=cycle.begin(), stop=cycle.end();
while (it != stop)
{
out<<*it<<" ";
++it;
}
return 0;
}