Cod sursa(job #3224788)

Utilizator MagicantPlusIuoras Andrei MagicantPlus Data 16 aprilie 2024 11:08:29
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <forward_list>
#include <unordered_set>
#include <stack>

using namespace std;

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

void euler(int start, vector<unordered_multiset<int>> &adjacent, forward_list<int> &cycle);

int main()
{
    long long n, m;
    vector<unordered_multiset<int>> adjacent;
    forward_list<int> cycle;

    fin >> n >> m;
    vector<long long> grade(n, 0);
    adjacent.resize(n);

    for(int i = 0; i < m; i++)
    {
        int l, r;

        fin >> l >> r;
        l--;
        r--;

        grade[l]++;
        grade[r]++;

        adjacent[l].insert(r);
        adjacent[r].insert(l);
    }

    for(int i = 0; i < grade.size(); i++)
    {
        if(grade[i] % 2 == 1)
        {
            fout << "-1";
            return 0;
        }
    }
    
    euler(0, adjacent, cycle);

    for(auto &e : cycle)
    {
        fout << e + 1 << ' ';
    }

    return 0;
}

void euler(int start, vector<unordered_multiset<int>> &adjacent, forward_list<int> &cycle)
{
    stack<int> next;
    int node, neighbor;

    next.push(start);

    while(!next.empty())
    {
        node = next.top();
        
        if(!adjacent[node].empty())
        {
            neighbor = *adjacent[node].begin();
            next.push(neighbor);
            adjacent[node].erase(adjacent[node].begin());
            adjacent[neighbor].erase(adjacent[neighbor].find(node));

            continue;
        }

        cycle.push_front(node);
        next.pop();
    }
}