Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
tvboy
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 99
#1

В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве. - C++

09.06.2013, 16:57. Просмотров 294. Ответов 0
Метки нет (Все метки)

Изолированные города

В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве.

Формат входного файла

Во входном файле записаны сначала два числа N и M, задающие соответственно количество городов и количество дорог (1≤N≤100, 0≤M≤1000), а затем перечисляются попарно связанные дорогами города. Каждая дорога задается номерами городов, которые она соединяет.
Формат выходного файла

В выходной файл выведите одно число – количество штатов в государстве.

Примеры:

input.txt 6 3 1 3 1 5 2 6 output.txt 3

0. Предпринять действия, позволяющие в дальнейшем оптимальнее искать города, соединенные дорогами с данным:
0.1. Определяем структура из двух чисел, описывающая дорогу.
0.2. Заводим массив этих структур длиной 2М.
0.3. Каждую считанную дорогу записываем в этот массив дважды: в прямом и обратном направлении.
0.4. Сортируем массив по первому полю для обеспечения бинарного поиска.
Таким образом сокращаем как объем необходимой памяти, так и сложность алгоритма.

Ребята помогите пожалуйста буду очень благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2013, 16:57     В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве.
Посмотрите здесь:

C++ Как связать элементы массивов между собой
C++ Сколько штатов в государстве (перевод с С на С++)
Напечатать все пары городов, связанных между собой не напрямую, но не более чем с одной пересадкой C++
Программа определяет, сколько точек пересечения образуют по этим координатам окружности C++
C++ Программа определяет, сколько точек пересечения образуют по координатам окружности
Существует N городов для каждой пары городов (і, j) можно построить путь C++
C++ Заданы массивы: города и население. Вывести список городов в порядке возрастания населения
Сравнить строки из файла между собой C++
На олимпиаду прибыло N человек. Некоторые из них знакомы между собой C++
C++ Задачку про три города не связанных между собой

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 16:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru