Блог

Я работал над проблемой, которую решил, но я не уверен, что это лучший способ сделать это. Я работаю в Windows 10 с visual studio. Я знаю, что использую компилятор c , но код должен быть на C.

Проблема: На поверхности Марса есть N городов, соединенных M дорогами, люди хотят уничтожить дороги, но только стратегические дороги. Дорога является стратегической тогда и только тогда, когда без этой дороги пара городов больше не соединена. Поскольку люди собираются разрушить некоторые дороги, они строят новую дорогу.

Ввод: файл .txt, в первой строке 3 числа N, M, Q, следующая строка M-это ссылка на поверхность Марса, следующие строки Q содержат дороги, которые собираются построить марсиане.

input.txt

 5 4 2 5 1 3 2 2 5 4 2 1 2 5 3  

Выход: Q строка, содержащая количество стратегических дорог после добавления каждой строки.

пример вывода:

 2 1  

Я решил создать динамический массив и добавить город, если он связан с другим городом в массиве, если в конце цикла 2 города не находятся в массиве, дорога, которая соединяет эти два города, не является стратегической.

 #includelt;assert.hgt; #includelt;stdio.hgt; #includelt;malloc.hgt;  #define MAX_LINKS (250000)  typedef struct {  int a;  int b; } link_t;  int N, M, Q, L, i; link_t links[MAX_LINKS];  int find(int, int*, int); bool strategic(link_t);  int main() {   freopen("input.txt", "r", stdin);   assert(scanf("%d%d%d", amp;N, amp;M, amp;Q)==3);  for (i = 0; i lt; M;   i) {  assert(scanf("%d%d", amp;links[i].a, amp;links[i].b)==2);    L;  }  int strategic_roads;  for (i = 0; i lt; Q;   i) {  assert(scanf("%d%d", amp;links[M   i].a, amp;links[M   i].b) == 2);    L;  strategic_roads = 0;  for (int j = 0; j lt; L;   j) {  if (strategic(links[j])) {    strategic_roads;  }  }  printf("%dn", strategic_roads);  } }  int find(int val, int* array, int size) {  for (int i = 0; i lt; size;   i) {  if (array[i] == val) {  return i;  }  }  return -1; }  bool strategic(link_t link) {  int counter = 1, size = 1, *arr;  int find_a = 0, find_b = 0;  arr = (int*)malloc(size * sizeof(int));  arr[0] = link.a;  bool still_working;  do {  still_working = false;  for (int i = 0; i lt; L;   i) {   if ((links[i].a == link.a amp;amp; links[i].b == link.b) || (links[i].a == link.b amp;amp; links[i].b == link.a)) {  continue;  }   find_a = find(links[i].a, arr, size);  find_b = find(links[i].b, arr, size);   if (find_a lt; 0 amp;amp; find_b gt;= 0) {    size;  arr = (int*) realloc(arr, size * sizeof(int));  arr[counter] = links[i].a;    counter;  still_working = true;  }   else if (find_a gt;= 0 amp;amp; find_b lt; 0) {    size;  arr = (int*)realloc(arr, size * sizeof(int));  arr[counter] = links[i].b;    counter;  still_working = true;  }   }  } while (still_working);  return (find(link.b, arr, size) lt; 0); }  

Знаете ли вы другой лучший способ решить эту проблему?