Algorytm Kruskala - sprawdzenie poprawności

Panowie, czy ten algorytm działa prawidłowo?

#include <iostream>
#include <fstream>
#include <list>
#include <sstream>
using namespace std;

class Edge
{
    public:
        int weight;
        int p1,p2;
        Edge()
        {
            weight=0;
            p1=0;
            p2=0;
        }
        Edge(int _weight , int _p1, int _p2)
        {
            weight=_weight;
            p1=_p1;
            p2=_p2;
        }

        void wypisz()
        {
            cout  << "waga="<< weight << " p1=" <<p1 << " p2="<< p2 <<" " << endl;
        }
};

Edge *pom;

void scal(Edge tab[], int lewy, int srodek, int prawy)
{
  int i = lewy, j = srodek + 1;
  for(int i = lewy;i<=prawy; i++)
    pom[i] = tab[i];
  for(int k=lewy;k<=prawy;k++)
  if(i<=srodek)
    if(j <= prawy)
         if(pom[j].weight<pom[i].weight)
             tab[k] = pom[j++];
         else
             tab[k] = pom[i++];
    else
        tab[k] = pom[i++];
  else
      tab[k] = pom[j++];
}

void sortowanie_przez_scalanie(Edge tab[],int lewy, int prawy)
{
  if(prawy<=lewy) return;
  int srodek = (prawy+lewy)/2;
  sortowanie_przez_scalanie(tab, lewy, srodek);
  sortowanie_przez_scalanie(tab, srodek+1, prawy);
  scal(tab, lewy, srodek, prawy);
}

class Kruskal
{
public:
    Edge * wynik;
    int sumaD=0;
    Kruskal (Edge *tab, int w,int m)
    {
        int * zbiory = new int  [w+1];
        wynik = new Edge [w-1];
        int wierzcholek=0;
        for (int i = 0 ; i < m;i++ )
        {
            if (wierzcholek == w-1)
            {
                break;
            }
            if(zbiory[tab[i].p1] == 0 || zbiory[tab[i].p1] != zbiory[tab[i].p2])
            {
                wynik[wierzcholek] = tab[i];
                sumaD += tab[i].weight;
                wierzcholek++;
                if(zbiory[tab[i].p1] !=0 || zbiory[tab[i].p2] !=0)
                {
                    int zbior1 = zbiory[tab[i].p1];
                    int zbior2 = zbiory[tab[i].p2];
                    for (int j = 0 ; j< w; j ++)
                    {
                        if(zbiory[j] != 0 &&(zbiory[j] == zbior1 || zbiory[j] == zbior2))
                        {
                            zbiory[j]=wierzcholek;
                        }
                    }
                }
                zbiory[tab[i].p1]=wierzcholek;
                zbiory[tab[i].p2]=wierzcholek;
            }
        }
    }

};
int main()
{
    fstream plik;
    plik.open("In.txt",ios::in);
    if(plik.good()== false)
    {
        cout << "nie otwiera sie plik " ;
        return 1;
    }
    int n,m;
    plik >> n >> m;
    Edge * Krawedzie = new Edge [2*m];
    string buffor;
    int liczba1,liczba2,licz=0;
    char b;
    for (int i =0 ; i <= n; i++)
    {
        getline(plik,buffor);
        istringstream zmienna(buffor);
        cout << buffor<< endl;
        while (zmienna >> liczba1)
        {
            zmienna >> liczba2;
            zmienna >> b;
            Krawedzie[licz].weight = liczba2;
            Krawedzie[licz].p1 = i;
            Krawedzie[licz].p2 = liczba1;
            licz++;
        }
    }
    pom = new Edge [2*m];
    sortowanie_przez_scalanie(Krawedzie,0,(2*m)-1);
    for (int i = 0 ; i < 2*m ;i++)
    {
        Krawedzie[i].wypisz();
    }
    delete [] pom ;
    plik.close();
    plik.open("Out.txt",ios::out);
    if(plik.good()== false)
    {
        cout << "nie otwiera sie plik " ;
        return 1;
    }
    Kruskal kru(Krawedzie,n,2*m);
    plik << kru.sumaD << endl;
    for (int i = 0 ; i < n-1 ; i++)
    {
       plik << kru.wynik[i].p1 << " " <<  kru.wynik[i].p2 << " [" << kru.wynik[i].weight << "],";
    }
    plik.close();
    return 0;
}

Po wprowadzeniu liczb z polecenia, nieco inaczej jest.
Mój Out.txt

16
3 9 [1],4 9 [1],5 6 [1],6 9 [2],7 9 [2],8 9 [2],1 2 [3],1 8 [4],

Panowie, czy ten algorytm działa prawidłowo?

Znajdź jakiś najprostszy przypadek, i testuj + debugger.

Napisz test, najlepiej "data driven test".
za pomocą gest: https://godbolt.org/z/M1vYWd
albo Catch2: https://godbolt.org/z/PWrccT

W dobrej praktyce programowania od tego się zaczyna: najpierw pisze test, a potem kod, który wypełnia warunki testu.

Rafał Masny napisał(a):

Po wprowadzeniu liczb z polecenia, nieco inaczej jest.
Mój Out.txt

16
3 9 [1],4 9 [1],5 6 [1],6 9 [2],7 9 [2],8 9 [2],1 2 [3],1 8 [4],

Różnice między Twoim rozwiązaniem a podanym w zadaniu są 2:

1. Kolejność krawędzi grafu - chyba nie ma znaczenia
2. Waga dla krawędzi 4 9 wynosi [2], co zresztą widać w podanym pliku - piąta linijka pokazuje, na końcu 9 2 (czyli waga 2 dla połączenia 4 9) a u Ciebie jest [1], więc tu jest błąd.