Prim(R)

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

#define MAX_LENGTH_ARC 501501
#define MAX_COUNTR_VERTEX 1003

char arc[MAX_LENGTH_ARC];// edges
int number[MAX_LENGTH_ARC];//   number of edges
int last[MAX_COUNTR_VERTEX]; //vertex for MST
char mark[MAX_COUNTR_VERTEX]; //old vertex from all graph
int edge_num_MST[MAX_COUNTR_VERTEX];// result

//make "index" from v
int makeIndex(int vert1, int vert2) {
    if (vert1 > vert2) {
        return (vert1 * (vert1 - 1)) / 2 + vert2;
    } else {
        return (vert2 * (vert2 - 1)) / 2 + vert1;
    }
}

int prim(int n, int v) {
    char dist[MAX_COUNTR_VERTEX];
    for (int i = 0; i < MAX_COUNTR_VERTEX; i++) {
        dist[i] = 'c';
    }
    for (int i = 0; i < n; i++) {
        last[i] = -2000000;
        dist[i] = 'a';
    }
    int index = 0, k = 0;

    dist[v] = '/';
    for (int i = 0; i < n; i++) {
        v = 1002;
        for (int j = 0; j < n; j++) {
            if (mark[j] == '-' && (dist[j] < dist[v])) {
                v = j;
            }
        }
        mark[v] = '+';

        if (last[v] != -2000000) {
            index = makeIndex(v, last[v]);
            edge_num_MST[k] = number[index];
            k++;
        }

        for (int j = 0; j < n; j++) {
            index = makeIndex(v, j);
            if (arc[index] != ' ') {
                if (arc[index] < dist[j]) {
                    dist[j] = arc[index];
                    last[j] = v;
                }
            }
        }
    }
    return k;
}

int main() {
    // initialization
    for (int i = 0; i < MAX_COUNTR_VERTEX; i++) {
        mark[i] = '-';
        last[i] = -2000001;
    }
    for(int i = 0; i < MAX_LENGTH_ARC; i++) {
        arc[i] = 'a';
        number[i] = 2000;
    }

    FILE *input = fopen("input.txt", "r");
    FILE *output = fopen("output.txt", "w");

    int n, m;
    fscanf(input, "%d\n", &n);
    fscanf(input, "%d\n", &m);

    for(int i = 0; i < m; i++) {
        int vert1, vert2, edge, index;
        fscanf(input, "%d %d %d", &vert1, &vert2, &edge);
        index = makeIndex(vert1, vert2);
        arc[index] = edge - 1;//for translate to char
        number[index] = i;
    }

    int c = prim(n, 0) + 1;
    // sort result
    for(int i = 0; i < c; i++) {
        for(int j = 0; j < c - 1; j++) {
            if(edge_num_MST[j + 1] < edge_num_MST[j]) {
                int k = edge_num_MST[j];
                edge_num_MST[j] = edge_num_MST[j + 1];
                edge_num_MST[j + 1] = k;
            }
        }
    }
    //print result
    for(int i = 1; i < c; i++) {
        fprintf(output, "%d\n", edge_num_MST[i]);
    }

    fclose(input);
    fclose(output);

    return 0;
}