Cod sursa(job #2815004)

Utilizator realmeabefirhuja petru realmeabefir Data 8 decembrie 2021 22:51:00
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

vector<pair<int, int>> la[100005];
int n, m;
int edge_used[500005];

struct node
{
    node* prev = nullptr;
    node* next = nullptr;
    int val;
};

node* current_node = nullptr;

void dfs(int from)
{
    while (la[from].size())
    {
        int to = la[from].back().first;
        int added_at = la[from].back().first;
        la[from].pop_back();
        // daca mai avem muchii de la from la to
        if (edge_used[added_at])
            continue;

        edge_used[added_at] = 1;

        // foloseste muchia
        node* new_node = new node({current_node, current_node->next, to});
        current_node->next = new_node;
        current_node = new_node;
        dfs(to);
    }

    current_node = current_node->prev;
}

int main()
{
    in >> n >> m;
    while (m --)
    {
        int x, y;
        in >> x >> y;
        la[x].push_back({y, m});
        la[y].push_back({x, m});
    }

    for(int i=1; i<=n; i++)
    {
        if(la[i].size() % 2!=0)
        {
            out<<-1;
            return 0;
        }
    }

    int s = 1;
    node* start = new node({nullptr, nullptr, s});
    current_node = start;

    dfs(s);

    current_node = start;
    while (current_node->next != nullptr)
    {
        out << current_node->val << ' ';
        current_node = current_node->next;
    }

    return 0;
}