Pagini recente » Cod sursa (job #2261110) | Cod sursa (job #2663017) | Cod sursa (job #585299) | Cod sursa (job #558337) | Cod sursa (job #3281223)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector<pair<int,int>> graph[100001];
vector<int> cycle;
int grade[100001];
int visited[100001];
int visitedEdges[500001];
int currentEdge[100001];
void buildCycle(int node) {
while (currentEdge[node] < graph[node].size())
{
pair <int, int> edge = graph[node][currentEdge[node]];
currentEdge[node] ++;
if (visitedEdges[edge.second])
continue;
visitedEdges[edge.second] = 1;
buildCycle(edge.first);
}
cycle.push_back(node);
}
void dfs(int node)
{
visited[node]=1;
for(auto x : graph[node])
{
if(!visited[x.first])
dfs(x.first);
}
}
int main()
{
int n, m, x, y;
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>x>>y;
graph[x].push_back({y,i});
graph[y].push_back({x,i});
grade[x]++;
grade[y]++;
}
dfs(1);
for (int i = 1; i <= n; ++i) {
if (!visited[i] or grade[i] % 2) {
fout << -1;
return 0;
}
}
buildCycle(1);
cycle.pop_back();
for (auto x : cycle) {
fout << x << " ";
}
return 0;
}