Pagini recente » Cod sursa (job #993293) | Cod sursa (job #958332) | Cod sursa (job #2086082) | Cod sursa (job #1477834) | Cod sursa (job #2252525)
#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;
struct NodeStruct {
int Grad;
struct EdgeStruct {
int EdgeIndex, Dest;
}; std::list <EdgeStruct> ADC;
} Node[NNodes];
inline void AddEdge(int x, int y, int EdgeIndex) {
Node[x].ADC.push_back({EdgeIndex, y});
Node[y].ADC.push_back({EdgeIndex, x});
}
bool Preelim() {
for (int i=0; i<N; i++)
if (Node[i+1].Grad&1) return 0;
return 1;
}
bool Used[NEdges];
std::vector <int> Ciclu;
void DFS(int Index) {
for (auto Edge:Node[Index].ADC) {
if (!Used[Edge.EdgeIndex]) {
Used[Edge.EdgeIndex] = 1;
DFS(Edge.Dest);
}
} Ciclu.push_back(Index);
}
void FindEulerian() {
DFS(1);
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;
}