Kruskal and Prima algorithms

#include <iostream>
#include <time.h>

//кількість вершин
#define N 10

using namespace std;

//операції присвоювання, порівняння
int assignCount, compCount;

//час виконання
clock_t sTime, eTime;

//граф
class Graph {
    public:
        //кількість ребер
        int n;

        //матриця інцидентності
        int** c;

    public:
        Graph(int n) {
            c = new int* [n];

            for (int i = 0; i < n; i++) {
                c[i] = new int[n];

                for (int j = 0; j < n; j++) {
                    c[i][j] = -1;
                }
            }

            this->n = n;
        }

        //функція читання графа
        void set() {
            cout << "Enter graph:" << endl;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cin >> c[i][j];
                }
            }
        }

        //функція друкування графа
        void print() {
            cout << "   ";
            for (int i = 0; i < n; i++) {
                cout << i + 1 << " ";
            }
            cout << endl << "--";
            for (int i = 0; i < n; i++) {
                cout << "--";
            }
            cout << endl;
            for (int i = 0; i < n; i++) {
                cout << i + 1 << ": ";
                for (int j = 0; j < n; j++) {
                    if (c[i][j] > 0) {
                        cout << c[i][j] << " ";
                    } else {
                        cout << "  ";
                    }
                }
                cout << endl;
            }
            cout << endl;
        }

        friend Graph kruskalAlgo(Graph g, int& sum);

        friend int** getCArr(Graph &g, int &k);

        friend bool checkLoop(Graph &g, int u, int v, bool t[]);

        friend Graph primAlgo(Graph g, int &sum);
};

//функція для отримування масиву усіх ребер
int** getCArr(Graph &g, int &k) {
    k = 0;
    int n = g.n * (g.n - 1);
    int** cArr = new int* [n];

    for (int i = 0; i < n; i++) {
        cArr[i] = new int[3];
    }

    for (int i = 0; i < g.n; i++) {
        for (int j = 0; j < g.n; j++) {
            compCount++;
            if (g.c[i][j] > 0) {

                cArr[k][0] = i;
                cArr[k][1] = j;
                cArr[k][2] = g.c[i][j];

                assignCount += 3;

                k++;
            }
        }
    }
    return cArr;
}

//функці для сортування масиву усіх ребер у порядку зростання
void sortCArr(int** &cArr, int k) {
    for (int i = 1, j = i; i < k; i++, j = i) {
        while (j > 0 && cArr[j][2] < cArr[j - 1][2]) {
            compCount++;
            for (int k = 0; k < 3; k++) {
                swap(cArr[j][k], cArr[j - 1][k]);
            }
            assignCount += 3;
            j--;
        }
    }
}

//функція для перевірки того чи вершини u та v з'єднані
bool checkLoop(Graph &g, int u, int v, bool t[]) {
    if (t[u]) return false;
    if (u == v) return true;

    t[u] = true;
    assignCount++;

    for (int i = 0; i < g.n; i++) {
        if (g.c[u][i] > 0) {
            if (checkLoop(g, i, v, t) == true) {
                return true;
            }
        }
    }

    t[u] = false;

    return false;
}

//алгоритм Крускала
Graph kruskalAlgo(Graph g, int &sum) {
    Graph r(g.n);
    sum = 0;
    int k = 0, **cArr = getCArr(g, k);

    //отримуємо відсортований масив ребер по зростанню
    sortCArr(cArr, k);

    for (int i = 0, n = 0; i < k && n < r.n - 1; i++) {
        bool t[g.n] = { false };

        int u = cArr[i][0];
        int v = cArr[i][1];

        //якщо вставка мінімального ребра не утворить петлю то вставляємо ребро у граф
        if (checkLoop(r, u, v, t) == false) {
            r.c[u][v] = r.c[v][u] = cArr[i][2];
            n++;
            sum += cArr[i][2];
            assignCount += 2;
        }
    }
    return r;
}

//алгоритм Прима
Graph primAlgo(Graph g, int &sum) {
    Graph r(g.n);
    sum = 0;
    int k = 0, **cArr = getCArr(g, k);
    bool c[g.n] = { false };

    c[0] = true;
    //отримуємо відсортований масив ребер по зростанню
    sortCArr(cArr, k);

    for (int j = 0; j < r.n - 1; j++) {
        for (int i = 0; i < k; i++) {
            int u = cArr[i][0];
            int v = cArr[i][1];

            compCount += 2;

            //шукаємо манімальне ребро між вершиною у матриці С та вершиною якої немає у матриці С
            //та вставляємо це ребро у граф
            if (c[u] && not c[v]) {
                r.c[u][v] = r.c[v][u] = cArr[i][2];
                sum += cArr[i][2];
                c[v] = true;
                assignCount += 2;
                break;
            }
        }
    }
    return r;
}

int main() {
    int sum;
    Graph g(N);

    g.set();

    cout << endl << "Kruskal result:" << endl;
    assignCount = compCount = 0;
    sTime = clock();
    kruskalAlgo(g, sum).print();
    eTime = clock();

    cout << "assignment operations = " << assignCount << endl;
    cout << "comparison operations = " << compCount << endl;
    cout << "time = " << int(eTime - sTime) << endl;
    cout << "sum = " << sum << endl;

    cout << endl << "Prima result:" << endl;
    assignCount = compCount = 0;
    sTime = clock();
    primAlgo(g, sum).print();
    eTime = clock();

    cout << "assignment operations = " << assignCount << endl;
    cout << "comparison operations = " << compCount << endl;
    cout << "time = " << int(eTime - sTime) << endl;
    cout << "sum = " << sum << endl;

    return 0;
}