Pagini recente » Cod sursa (job #840371) | Cod sursa (job #1116778) | Cod sursa (job #1960201) | Cod sursa (job #1423260) | Cod sursa (job #1638026)
#include <fstream>
#include <stack>
#include <list>
#include <vector>
#include <algorithm>
constexpr int kMaxN = 100000;
int n, m;
std::list<int> edges[kMaxN+1];
std::vector<int> eulerian_circuit;
bool isEulerian()
{
for(int i = 1; i <= n; ++i)
if(edges[i].size()%2 == 1 || edges[i].size() == 0) return false;
return true;
}
void buildEulerianCircuit()
{
std::stack<int> S;
S.push(1);
while(!S.empty()) {
int x = S.top();
if(edges[x].size() == 0) {
eulerian_circuit.push_back(S.top());
S.pop();
}
else {
int y = edges[x].front();
edges[x].pop_front();
edges[y].erase(std::find(edges[y].begin(), edges[y].end(), x));
S.push(y);
}
}
}
int main()
{
std::ifstream in("ciclueuler.in");
std::ofstream out("ciclueuler.out");
in>>n>>m;
for(int x, y, i = 1; i <= m; ++i) {
in>>x>>y;
edges[x].push_back(y);
edges[y].push_back(x);
}
if(isEulerian()) {
buildEulerianCircuit();
eulerian_circuit.pop_back();
for(auto x : eulerian_circuit) out<<x<<' ';
}
else out<<"-1\n";
return 0;
}