| |
 4 Кб |
|
| | Здравствуйте!!!
Помогите решить задачу на с++
Вот такое условие:
Армия расположена на островах, соединенных так, что имеется сообщение между любыми двумя островами. Найти все такие мосты, уничтожив любой из которых можно разбить армию.
Задание надо сделать через графы. Начал решать, определил класс Граф как массив массивов.
Заранее спасибо. | |
| |
|
|
| |
|
|
| |
для: bober80
(12.01.2008 в 10:42)
| | | А можно поточнее? Что значит "разбить армию"? | |
| |
|
|
| |
|
|
| |
для: Фитч
(12.01.2008 в 11:03)
| | | возможно, разделить на 2 равные части....
а вообще, это боян, есть задача про компьютерную сеть где надо завалить какойто канал так
чтобы сеть разбилась на части.
Неэффективный алгоритм:
перебираем все ребра графов
для каждого ребра:
выбираем случайную вершину и отмечаем ее.
из вершины смотрим все соседние, отмечаем их, для соседних то же самое, и т. д....
в итоге, если останутся неотмеченные вершины,то даное ребро - искомое. | |
| |
|
|
