Monique

#include <stdio.h>
#include <iostream>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <ctime>
#include <algorithm>
#include <time.h>
#include <vector>
#include <map>

using namespace std;

class Krawedz
{
    public:
        int stad;
        int dokad;
        int waga;
};

int AlgorytmKruskala(int n, Krawedz **K1, Krawedz **K2 )
{

    int *A = (int*)malloc(sizeof(int) * (n + 3));
    //vector<int> B(0);
    int  j, k, u, v, w;
    int suma = 0;

    std::fill_n(A + 1, n, 0);

    k = 1;
    j = 1;
    while (k < n)
    {
        u = (*K1)[j].stad;
        v = (*K1)[j].dokad;
        j++;
        if ( A[u] == 0 || A[v] == 0 || A[u] != A[v] )
        {
            suma++;
            (*K2)[suma] = (*K1)[j - 1];
            if ( A[u] == 0 && A[v] != 0 )
            {
                w = u;
                u = v;
                v = w;
            }
            if (A[u] == 0) A[u] = u;

            if (A[v] == 0) A[v] = A[u];
            else
            {
                w = A[v];
                for (int i = 1; i <= n; i++)
                    if (A[i] == w ) A[i] = A[u];
            }
            k++;
        }
    }

    delete A;
    return suma;
}

bool operator < (const Krawedz &a, const Krawedz &b)
{
    return a.waga < b.waga;
}

int Porownaj(const void *a, const void *b)
{
   Krawedz *c = (Krawedz*)a;
   Krawedz *d = (Krawedz*)b;
   if (c -> waga < d -> waga) return -1;
   else if (c -> waga == d -> waga) return 0;
   else return 1;
}

int main()
{
    int n, k, suma, p, a = 0, y, x;

    srand((unsigned)time(NULL));

    cout << endl << endl << endl;
    cout << "\t..:: MODELOWANIE GRAFOW - ALGORYTM AlgorytmKruskalaA ::.." << endl;
    cout << "\t\tMonika Kosinska, 165060" << endl << endl;
    cout << "\t\tPodaj liczbe wierzcholkow: ";
    cin >> n;
    cout << endl;
    cout << "\t\tPodaj procentowa (%) ilosc krawedzi: ";
    cin >> k;
    cout << endl << endl;

    p = n * (n - 1) / 2 * k / 100;

    //Krawedz *K1 = (Krawedz*)malloc((p + 3)* sizeof(Krawedz));
    //Krawedz *K2 = (Krawedz*)malloc((p + 3)* sizeof(Krawedz));
    Krawedz* K1 = new Krawedz;
    Krawedz* K2 = new Krawedz;

     //osoba* czlowiek1 = new osoba;

    for (int i = 1; i <= n - 1; i++)
    {
        K1[i].stad = i;
        K1[i].dokad = i + 1;
        K1[i].waga = 1 + rand() % 10;
    }
    for (int i = n; i <= p;)
    {
        int q=0;
        y = 1 + rand() % (n);
        x = 1 + rand() % (n);
        if (x != y)
        {
            for (int j = 1; j <= p; j++)
            {

                if (K1[j].stad == x)
                    if (K1[j].dokad == y)
                    {
                        q = 1;
                    }
                if (K1[j].stad == y)
                    if (K1[j].dokad == x)
                    {
                        q = 1;
                    }
            }

            if (q == 0)
            {
                K1[i].stad = x;
                K1[i].dokad = y;
                K1[i + 1].stad = y; // gdy skierowany//
                K1[i + 1].dokad = x;//
                K1[i].waga = 1 + rand() % 9;
                K1[i + 1].waga = K1[i].waga;//
                i++;
            }
        }
    }

    cout << endl << endl << "\t\t\t MOJ WYGENEROWANY GRAF: " << endl << endl;

    for(int i = 1; i <= p; i++)
    {
        cout << "\t\t\t" << K1[i].stad << " -> " << K1[i].dokad << ": " << K1[i].waga << endl;
    }


    //trzeba policzyc czas trwania AlgorytmKruskalaa******************************

    clock_t StartTime, StopTime; //potrzebne dane do liczenia czasu trwania - bibloteka ctime

    StartTime = clock(); //uruchamiam zegar

    qsort(&K1, p, sizeof(Krawedz), Porownaj);

    suma = AlgorytmKruskala(n, &K1, &K2 );

    StopTime = clock(); //zatrzymuje zegar

    double czas = 0;

    czas = (StopTime - StartTime) /  (double) CLOCKS_PER_SEC; //licze czas

    //*********************************************************************

    int pom = 0;

    cout << endl << endl << "\t\t\tNAJKROTSZA DROGA W TYM GRAFIE TO: " << endl << endl;

    for (int i = 1; i <= suma; i++)
    {
        cout << "\t\t\t" << K2[i].stad << " -> " << K2[i].dokad << " : " << K2[i].waga << endl;
        pom += K2[i].waga;
    }
    cout << endl << endl << "\t\t\t\t" << "Wartość MST:  " << pom << endl;
    cout << endl << endl << "\t\t\t\t" << "Czas trwania AlgorytmKruskalaa: " << czas << "[s]" << endl << endl << "\t\t\t\t";
    delete K1;
    delete K2;
}