Cod sursa(job #3281223)

Utilizator Cristian_5APuscasu Marian Cristian Cristian_5A Data 28 februarie 2025 18:18:19
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#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;
}