Pagini recente » Cod sursa (job #56888) | Cod sursa (job #3223287) | Cod sursa (job #1263091) | Cod sursa (job #1516236) | Cod sursa (job #3266322)
// Hierholzer's Algorithm
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector<vector<pair<int, int>>> adj;
vector<bool> viz;
vector<int> ans;
int n, m, x, y;
bool IsEulerian()
{
for (int i = 1; i <= n; ++i)
if (adj[i].size() % 2)
return false;
return true;
}
void Dfs(int x)
{
while (!adj[x].empty())
{
auto &[y, edge] = adj[x].back();
adj[x].pop_back();
if (!viz[edge])
{
viz[edge] = true;
Dfs(y);
}
}
ans.push_back(x);
}
int main()
{
fin >> n >> m;
adj.resize(n + 1);
viz.resize(m + 1);
for(int i = 1; i <= m; ++i)
{
fin >> x >> y;
adj[x].push_back({y, i});
adj[y].push_back({x, i});
}
if (IsEulerian())
{
Dfs(1);
//reverse(ans.begin(), ans.end());
for(size_t i = 0; i < ans.size() - 1; ++i)
fout << ans[i] << " ";
}
else
fout << "-1";
return 0;
}