помогите люди добрые решить мне эту задачку уже мозг болит!!!!!!!
заранее спасибо!!!
В стране Флатландии N городов, соединенных М дорогами. По древней традиции, перемещаться по каждой дороге можно только в одну сторону.
Города Флатландии хотят объединиться в торговый союз. Как показали исследования, группа городов может объединиться в торговый союз, если для любых двух городов А и В из этой группы, либо из А можно добраться по дорогам страны в В, либо из В можно добраться по дорогам страны в А, либо то и другое одновременно. Считается, что минимальный торговый союз — это один город.
Ваша задача — по заданному плану дорог Флатландии определить наибольшее число городов, которые могут объединиться в торговый союз
помогите с задачей по паскалю!!!
Создать матрицу NxN: если из города i можно доехать до города j, то в матрице на месте [i,j] стоит 1, если нет, то 0.
Далее пройтись по каждой i-й строке матрицы: для любого j, такого что A[i,j]=1, надо пройтись по j-й строке матрицы, и для любого k, такого что A[j,k]=1, устанавливаем А[i,k]=1 (Если из i можно пройти в j, а из j в k - можно пройти из i в k).
Потом еще раз пройтись по таблице и найти такое i, для которого количество единиц в i-й строке и i-м столбце максимально. Эта сумма на единицу больше искомого результата
Далее пройтись по каждой i-й строке матрицы: для любого j, такого что A[i,j]=1, надо пройтись по j-й строке матрицы, и для любого k, такого что A[j,k]=1, устанавливаем А[i,k]=1 (Если из i можно пройти в j, а из j в k - можно пройти из i в k).
Потом еще раз пройтись по таблице и найти такое i, для которого количество единиц в i-й строке и i-м столбце максимально. Эта сумма на единицу больше искомого результата
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.