Pagini recente » Cod sursa (job #1139375) | Cod sursa (job #1026025) | Cod sursa (job #1702006) | Cod sursa (job #1530802) | Cod sursa (job #2252552)
#include <bits/stdc++.h>
#define MaxN 100005
#define MaxM 500005
std::ifstream InFile("ciclueuler.in");
std::ofstream OutFile("ciclueuler.out");
template <int NNodes, int NEdges>
struct GraphStruct {
int N, M;
std::vector <std::pair <int, int>> Edges;
struct NodeStruct {
int Grad;
std::vector <int> Edges;
} Node[NNodes];
inline void AddEdge(int x, int y, int EdgeIndex) {
Node[x].Edges.push_back(EdgeIndex);
Node[y].Edges.push_back(EdgeIndex);
Node[x].Grad++; Node[y].Grad++;
Edges.push_back(std::make_pair(x, y));
}
bool Preelim() {
for (int i=0; i<N; i++)
if (Node[i+1].Grad%2 == 1) return 0;
return 1;
}
int P[MaxN];
bool Used[NEdges];
std::vector <int> Ciclu;
void DFS(int Index) {
int EdgeIndex;
while(P[Index] < Node[Index].Edges.size()) {
EdgeIndex = Node[Index].Edges[P[Index]++];
if (!Used[EdgeIndex]) {
Used[EdgeIndex] = 1;
DFS(Edges[EdgeIndex].first + Edges[EdgeIndex].second - Index);
}
} Ciclu.push_back(Index);
}
void FindEulerian() {
DFS(Edges[0].first);
for (int i=1; i<Ciclu.size(); ++i)
OutFile << Ciclu[i] << ' ' ;
}
}; GraphStruct <MaxN, MaxM> Graph;
void Citire() {
InFile >> Graph.N >> Graph.M;
for (int i=0, x, y; i<Graph.M; i++)
InFile >> x >> y,
Graph.AddEdge(x, y, i);
}
void Rezolvare() {
if(Graph.Preelim())
Graph.FindEulerian();
else OutFile << "-1\n";
}
int main()
{
Citire();
Rezolvare();
return 0;
}