dz5

#include "stdlib.h"
#include "stdio.h"
#define N 100 // Максимальное кол-во вершин
#define M 100 // Максимальное кол-во рёбер

struct Edge {
  int v1, v2;
};

int vertex[N];
int vertexDegree[N] = {0};
struct Edge graph[M];

int wall(int left, int right) {
  int x = vertexDegree[vertex[left]];
  int i = left + 1;
  int j = right;
  do {
    while ((i <= j) && (vertexDegree[vertex[i]] <= x))
        i++;
    while ((i <= j) && (vertexDegree[vertex[j]] >= x))
        j--;
    if (i < j) {
      int temp1;
      temp1 = vertex[i];
      vertex[i] = vertex[j];
      vertex[j] = temp1;
      i++;
      j--;
    }
  } while (i < j);
  int temp2;
  temp2 = vertex[left];
  vertex[left] = vertex[j];
  vertex[j] = temp2;
  return j;
}

void quick_sort(int begin, int end) {
  int k;
  if (begin < end) {
      k = wall(begin, end);
      quick_sort(begin, k - 1);
      quick_sort(k + 1, end);
  }
}

int main() {
  int n, m, i, j, v1, v2;
  printf("Количество вершин: ");
  scanf("%d", &n);
  printf("Количество рёбер: ");
  scanf("%d", &m);
  printf("Рёбра:\n");
  for (i = 0; i < m; i++) {
    scanf("%d %d", &v1, &v2);
    if (v1 <= 0 || v1 > n || v2 <= 0 || v2 > n) {
      printf("Недопустимый номер вершины.\n");
      return 1;
    }
    graph[i].v1 = v1 - 1;
    graph[i].v2 = v2 - 1;
    vertexDegree[v1 - 1]++;
    vertexDegree[v2 - 1]++;
  }

  printf("Удаление ребра. Введите номер ребра: ");
  scanf("%d", &j);
  if (j <= 0 || j > m) {
    printf("Недопустимый номер ребра.\n");
    return 1;
  }
  vertexDegree[graph[j - 1].v1]--;
  vertexDegree[graph[j - 1].v2]--;
  graph[j - 1].v1 = graph[j - 1].v2 = -1;
  printf("Ребро удалено\n");

  for (i = 0; i < n; i++)
    vertex[i] = i;

  quick_sort(0, n - 1);

  for (i = n - 1; i >= 0; i--)
    printf("%d: %d\n", vertex[i] + 1, vertexDegree[vertex[i]]);

  return 0;
}