Skip to content

Instantly share code, notes, and snippets.

@Glavak

Glavak/Prim.cs

Created April 5, 2019 06:31
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Glavak/34233e715590edcc58a98e58a251cc47 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Glavak/34233e715590edcc58a98e58a251cc47 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Glavak created this gist Apr 5, 2019.
    132 changes: 132 additions & 0 deletions Prim.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,132 @@
    #include <stdlib.h>
    #include <stdio.h>

    typedef struct rebro {
    int begin;
    int end;
    int length;
    } rebro_t;

    int count_ver;
    int count_rebro;
    rebro_t * all_rebro;

    int * visited_vertices; // 0 - пока не в ответе, 1 - в ответе
    rebro_t *rebro_answer;
    int count_rebro_already_added = 0;

    int cmp(rebro_t *a, rebro_t *b)
    {
    return a->length - b->length;
    }

    int process()
    {
    while (count_rebro_already_added != count_ver - 1)
    {
    int min_rebro = -1;
    for (int i = 0; i < count_rebro; i++)
    {
    int visited_begin = visited_vertices[all_rebro[i].begin];
    int visited_end = visited_vertices[all_rebro[i].end];
    if ((visited_begin == 0 && visited_end != 0) || (visited_begin != 0 && visited_end == 0))
    {
    min_rebro = i;
    break;
    }
    }
    if (min_rebro == -1)
    return 1;
    rebro_answer[count_rebro_already_added] = all_rebro[min_rebro];
    count_rebro_already_added++;
    visited_vertices[all_rebro[min_rebro].begin] = 1;
    visited_vertices[all_rebro[min_rebro].end] = 1;
    }

    return 0;
    }

    int main()
    {
    scanf("%d\n", &count_ver);
    if (count_ver < 0 || count_ver>5000)
    {
    printf("bad number of vertices");
    return 0;
    }
    else if (count_ver == 0)
    {
    printf("no spanning tree");
    return 0;
    }

    if (scanf("%d\n", &count_rebro) != 1) {
    printf("bad number of lines");
    return 0;
    }
    if (count_rebro<0 || count_rebro>((count_ver)*(count_ver + 1)) / 2)
    {
    printf("bad number of edges");
    return 0;
    }

    if (count_rebro > 0 && feof(stdin))
    {
    printf("bad number of lines");
    return 0;
    }

    all_rebro = malloc(sizeof(rebro_t)*count_rebro);
    rebro_answer = malloc(sizeof(rebro_t)*count_ver);
    visited_vertices = calloc(sizeof(int), (count_ver + 1));

    for (int i = 0; i < count_rebro; ++i)
    {
    scanf("%d %d %d\n", &all_rebro[i].begin, &all_rebro[i].end, &all_rebro[i].length);

    if (all_rebro[i].begin < 1 || all_rebro[i].begin > count_ver ||
    all_rebro[i].end < 1 || all_rebro[i].end > count_ver)
    {
    printf("bad vertex");
    free(all_rebro);
    free(visited_vertices);
    free(rebro_answer);
    return 0;
    }

    if (i < count_rebro - 1 && feof(stdin))
    {
    printf("bad number of lines");
    free(all_rebro);
    free(visited_vertices);
    free(rebro_answer);
    return 0;
    }
    if (all_rebro[i].length < 0)
    {
    printf("bad length");
    free(all_rebro);
    free(visited_vertices);
    free(rebro_answer);
    return 0;
    }
    }

    qsort(all_rebro, count_rebro, sizeof(rebro_t), cmp);

    visited_vertices[1] = 1;

    if (process() == 1)
    {
    printf("no spanning tree");
    }
    else
    for (int i = 0; i < count_ver - 1; i++)
    printf("%d %d\n", rebro_answer[i].begin, rebro_answer[i].end);

    free(all_rebro);
    free(visited_vertices);
    free(rebro_answer);

    return 0;
    }