Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
tvboy
0 / 0 / 0
Регистрация: 24.01.2013
Сообщений: 99
1

Алгоритмы на графах

09.06.2013, 07:28. Просмотров 587. Ответов 1
Метки нет (Все метки)

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

В государстве 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. Сортируем массив по первому полю для обеспечения бинарного поиска.
Таким образом сокращаем как объем необходимой памяти, так и сложность алгоритма.

Ребята помогите пожалуйста буду очень благодарен.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2013, 07:28
Ответы с готовыми решениями:

Вопросы о графах
Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф...

Задания по графах
1) Узнать не пустой ли граф 2) Запретить работу если начало и конец графа ...

Игры на графах
Помогите пожалуйста 😊 Имя входного файла: стандартный ввод Имя выходного...

"Поиск путей на графах". С++
Задача. Для некоторого ориентированного графа задана матрица весов W. С...

Алгоритмы на C++
Вот решил приобрести себе такую ​​книгу....

1
Catstail
Модератор
23623 / 11723 / 2047
Регистрация: 12.02.2012
Сообщений: 19,120
09.06.2013, 09:54 2
мне кажется, здесь проще поступить так:
0) обнулить число штатов
1) из номеров дорог построить матрицу смежности;
2) из первого еще не посещенного города выполнить обход графа (в глубину или ширину - неважно);
3) увеличить число штатов на 1
4) проверить, есть ли непосещенные города
4a) нет - вывести число штатов -> конец
4b) да - на п. 2
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 09:54

Алгоритмы С++
Написать программу календарь, которая при вводе даты выдает день недели

Алгоритмы
case 2:{ int n1; int n2; do{ cout <<...

Циклические алгоритмы
Как реализовать данную функцию для каждого x, изменяющегося от a до b с шагом...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru