#include <ctime>
#include <iostream>
#include <fstream>

using namespace std;

unsigned long long compare = 0, assign = 0; // оепратор сравнения и присваивания

#define Infinity 1000000
#define in_file "input.txt"
#define _x 0
#define _y 1
#define _z 2

class graph {
private:

    int** G; // таблица смежности графа
    int** T; // остовное дерево
    int* parent; // массив кластеров
    int V, R; // кол-во вершин и ребёр

public:
    void union_set(int r, int v); // функция создания кластеров
    int find_set(int i); // функция для нахождения нужных вершин
    void kraskal(); // алгоритм Краскала
    void prima(); // алгоритм Прима

    graph(string file) {
        ifstream in(file);
        if (in.is_open()) {
            in >> V;
            in >> R;
            G = new int* [V];
            parent = new int[V];
            for (int i = 0; i < V; i++) {
                G[i] = new int[V];
                parent[i] = i;
                for (int j = 0; i < V; j++)
                    in >> G[i][j];
            }
        }
        else {
            cout << "File is not found. Try again." << endl;
            G = NULL;
        }
        T = new int* [V - 1];
        for (int i = 0; i < V - 1; i++) {
            T[i] = new int[3];
        }
    }
    int** setGk() {
        int** Gk = new int* [0];
        for (int i = 0; i < R; i++)
            Gk[i] = new int[3];

        int k = 0;
        for (int i = 0; i < V; i++) {
            for (int j = i; j < V; j++) {
                if (G[i][j] != 0) {
                    Gk[k][_z] = G[i][j];
                    Gk[k][_x] = i;
                    Gk[k][_y] = j;
                    k++;
                }
            }
        }
        return Gk;
    }

    void print() {
        if (G == NULL)
            return;

        ofstream out_res("output.txt", ios::app);
        out_res << "Edge: " << "Weight:" << endl;
        for (int i = 0; i < V - 1; i++)
            out_res << T[i][_x] << " - " << T[i][_y] << " : " << T[i][_z] << endl;
    }
};

void sortGk(int** Gk, int R) { // сортировка графа в порядке возрастания (пузырьком)
    for (int i = 1; i < R; i++) {
        compare++;
        assign++;
        for (int j = 0; j < R - i; j++) {
            assign++;
            compare++;
            if (Gk[j][_z] > Gk[j + 1][_z]) {
                compare++;
                int* tmp = Gk[j];
                Gk[j] = Gk[j + 1];
                Gk[j + 1] = tmp;
            }
        }
    }
}

int graph::find_set(int i) {
    if (i == parent[i]) {
        compare++;
        return i;
    }
    else
        return find_set(parent[i]);
}

void graph::union_set(int r, int v) {
    parent[r] = parent[v];
    assign++;
}

void graph::kraskal() {
    if (G == NULL)
        return;
    compare = 0, assign = 0;


    int k = 0, uRep, vRep;
    int** Gk = setGk(); // сортируем граф
    sortGk(Gk, R);
    for (int i = 0; i < R; i++) {
        compare++;
        uRep = find_set(Gk[i][_x]);
        vRep = find_set(Gk[i][_y]);
        assign += 2;
        if (uRep != vRep) {  // Если не удается создать цикл, тогда добавляем ребро в остовное дерево
            T[k][_x] = Gk[i][_x] + 1;
            T[k][_y] = Gk[i][_y] + 1;
            T[k][_z] = Gk[i][_z];
            k++;
            assign += 4; // добавляем кластер
            union_set(uRep, vRep);
        }
    }
}

void graph::prima() {
    return;
    compare = 0, assign = 0;
    bool* selected = new bool[V]();
    int no_edge = 0;
    selected[0] = true;
    assign += 2;
    while (no_edge < V - 1) { // коли вершина входить в остове дерево, то ми її помічаємо. Вибираємо 2 вершини, щоб вони не з одної множини складувались.
        if (G == NULL)
            compare++;
        int min = Infinity;
        int x = 0, y = 0;
        assign += 3;

        for (int i = 0; i < V; i++) {
            assign++;
            compare++;
            if (selected[i]) {
                compare++;
                for (int j = 0; j < V; j++) {
                    compare++;
                    if (!selected[j] && G[i][j]) {
                        compare += 2;
                        if (min > G[i][j]) {
                            compare++;
                            min = G[i][j];
                            x = i;
                            y = j;
                            assign += 3;
                        }
                    }
                }
            }
        }
        T[no_edge][_x] = x + 1;
        T[no_edge][_y] = y + 1;
        T[no_edge][_z] = min;
        selected[y] = true;
        no_edge++;
        assign += 5;
    }
}

int main() {
    graph g(in_file);
    ofstream out_res;
    out_res.open("output.txt");
    out_res << "Algorithm of Kraskala: " << endl;
    out_res.close();
    unsigned long long Time = clock();
    g.kraskal();
    Time = clock() - Time;
    g.print();
    ofstream out_log;
    out_log.open("report.txt");
    out_log << "Algorithm of Kraskala: " << endl;
    out_log << "Time: " << Time << "ms" << endl;
    out_log << "Assign operations:" << assign << endl;
    out_log << "Compare operations: " << compare << endl;
    out_log.close();

    out_res.open("output.txt", ios::app);
    out_res << endl << "Algorithm of Prima: " << endl;
    out_res.close();
    Time = clock();
    g.prima();
    Time = clock() - Time;
    g.print();
    out_log.open("report.txt", ios::app);
    out_log << endl << "Algorithm of Prima: " << endl;
    out_log << "Time: " << Time << "ms" << endl;
    out_log << "Assign operations: " << assign << endl;
    out_log << "Compare operations: " << compare << endl;
    out_log.close();

    cout << "Operation completed successfully" << endl;
    return 0;
}