#include <stdlib.h>
#include <stdio.h>
#include <locale>

int dots;
int **graph;

struct root{
	int start;
	int end;
	int v;
};

root *roots;
root *ostgraph;

int main(){
	int counter = 0;
	setlocale(LC_ALL,"RUSSIAN");
	printf("Введите количество вершин в графе :");
	scanf("%d", &dots);
	graph = (int **)malloc(dots * sizeof(int));
	for (int i = 0; i < dots; i++)
		graph[i] = (int *)malloc(dots * sizeof(int));
	FILE *input = fopen("graph.txt", "r");
	if (input == NULL)
		printf("Невозможно открыть файл с графом \n");
	else{
		for (int i = 0; i < dots; i++){
			for (int j = 0; j < dots; j++){
				fscanf(input, "%d", &graph[i][j]);
				if (graph[i][j]>0)
					counter++;
			}
		}
		counter /= 2;
		printf("counter : %d \n", counter);
		roots = (root*)malloc(counter*sizeof(root)); // храним ребра
		ostgraph = (root*)malloc((dots - 1)*sizeof(root));
		int step = 0;
		bool target = true;
		for (int i = 0; i < dots; i++){
			for (int j = 0; j < dots; j++){
				if (graph[i][j]>0){
					for (int s = 0; s < counter; s++){
						if (roots[s].start == j && roots[s].end == i)
							target = false;
					}
					if (target == true){
						roots[step].start = i;
						roots[step].end = j;
						roots[step].v = graph[i][j];
						step++;
					}
				}
				target = true;
			}
		}
		//сортировка
		root tmp;
		for (int i = 0; i < counter - 1; i++){
			for (int j = 0; j < counter - i - 1; j++){
				if (roots[j].v > roots[j + 1].v){
					tmp.v = roots[j].v;
					tmp.start = roots[j].start;
					tmp.end = roots[j].end;
					roots[j].v = roots[j + 1].v;
					roots[j].start = roots[j + 1].start;
					roots[j].end = roots[j + 1].end;
					roots[j + 1].v = tmp.v;
					roots[j + 1].start = tmp.start;
					roots[j + 1].end = tmp.end;
				}
			}
		}
		for (int i = 0; i < counter; i++){
			printf("начало : %d  конец: %d  вес: %d \n", roots[i].start, roots[i].end, roots[i].v);
		}
		//сам корявый алгоритм сделанный на коленке
		target = true;
		step = 0;
		for (int i = 0; i < counter; i++){
			for (int j = 0; j < dots - 1; j++){
				if (roots[i].end == ostgraph[j].end){
					target = false;
				}
			}
			if (target == true){
				ostgraph[step].start = roots[i].start;
				ostgraph[step].end = roots[i].end;
				ostgraph[step].v = roots[i].v;
				step++;
			}
			target = true;
		}
		printf("\n\nНаш остовый граф: \n\n");
		for (int i = 0; i < dots-1; i++){
			printf("начало : %d  конец: %d  вес: %d \n", ostgraph[i].start, ostgraph[i].end, ostgraph[i].v);
		}
		//сохраняем в ебаный графиз мать его в кино водил
		FILE *inspect = fopen("graphviz.txt", "w+");
		fprintf(inspect, "graph G{\n");
		for (int i = 0; i < dots; i++){
			fprintf(inspect, "  %d;\n", i);
		}
		target = false;
		for (int i = 0; i < dots; i++){
			for (int j = 0; j < dots; j++){
				if (graph[i][j]>0){
					for (int s = 0; s < dots - 1; s++){
						if (ostgraph[s].start == i && ostgraph[s].end == j)
							target = true;
					}
					if (target == true)
							fprintf(inspect, "  %d -- %d [ label = \"%d\" color = \"RED\"];\n", i, j, graph[i][j]);
						else
							fprintf(inspect, "  %d -- %d [ label = \"%d\" color = \"BLACK\"];\n", i, j, graph[i][j]);
					target = false;
				}
			}
		}
		fprintf(inspect, "}");
		fclose(inspect);
	}
	fclose(input);
	free(graph);
	return 0;
}