algorytm wyznaczania cyklu Eulera - problem z działaniem

Question

Witam, mam problem z algorytmem wyznaczania cyklu Eulera w grafie nieskierowanym. Chcę zapisać algorytm wyszukiwania cyklu Eulera, opisany na tej stronie: https://eduinf.waw.pl/inf/alg/001_search/0135.php (chodzi o ten pierwszy algorytm wykrzystujący DFS_Postorder- nie Fleury ani Hierholzer), i moja poniższa implementacja w c++ jest zrobiona na tablicach list, a nie na macierzy sąsiedztwa, tak jak na stronie, i wywala mi błąd podczas przeszukiwania DFS, i potrzebuję pomocy kogoś doświadczonego, kto wskaże błędy w kodzie.

tutaj wklejam jeszcze test do algorytmu,  czyli graf, który posiada cykl Eulera:

6 10
1 5 1 6
2 3 2 4 2 5 2 6
3 4 3 5 3 6
5 6

Algorytm:

#include <iostream>
#include <list>
#include <stack>

using namespace std;

void DFS_EULER(int v, list<int> tab[], stack<int> Vertices)
{
    list<int>::iterator it;

    for(it = tab[v].begin(); it != tab[v].end(); it++)  //przeszukujemy sasiadow
    {
        tab[v].remove(*it);
        tab[*it].remove(v);  //usuwamy krawedzie
        DFS_EULER(*it, tab, Vertices); //wywolanie rekurencyjne
    }
    Vertices.push(v);
}

int main()
{
    int n, m, v1, v2;
    cin >> n >> m;
    //inkrementacja n i m, poniewaz wierzcholki beda wprowadzane od nr 1, a nie od 0
    n+=1;
    m+=1;

    list<int> *tab = new list<int>[n]; //utworzenie tablicy list, w której będzie graf

    for(int i = 1; i < m; i++)  //wczytywanie krawedzi grafu
    {
        cin >> v1 >> v2;
        tab[v1].push_back(v2);
        tab[v2].push_back(v1);
    }

    stack<int> Vertices;

    DFS_EULER(1, tab, Vertices);  //funkcja rekurencyjna wyznaczajaca wierzcholki cyklu eulera

    //wypisanie cyklu ze stosu
    cout << "Vertices: " << endl;
    while(Vertices.size() > 0)
    {
        cout << Vertices.top() << " ";
        Vertices.pop();
    }
    delete [] tab;

    return 0;
}

 

Answer 1

i moja poniższa implementacja w c++ jest zrobiona na tablicach list, a nie na macierzy sąsiedztwa

i to jest błąd. Usuwanie elementów z kontenera po którym iterujesz w pętli jest upierdliwe.

Sam nie wiem czy chciałoby mi się rozkminiać takie usuwanie 2 elementów z listy na dowolnej pozycji w pętli. Pewnie przez parę godzin. A niby coś o cpp wiem.