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

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

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

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

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

Ребята помогите пожалуйста буду очень благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2013, 07:28     Алгоритмы на графах
Посмотрите здесь:

Вопросы о графах - C++
Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как найти самый краткий путь между двумя...

Игры на графах - C++
Помогите пожалуйста 😊 Имя входного файла: стандартный ввод Имя выходного файла: Стандартный вывод Ограничение по времени:1 секунда ...

"Поиск путей на графах". С++ - C++
Задача. Для некоторого ориентированного графа задана матрица весов W. С помощью алгоритма Форда-Беллмана вычислить веса кратчайших...

Алгоритмы - C++
case 2:{ int n1; int n2; do{ cout << "Введите номер словаря в который хотите добавить ячейку: ...

алгоритмы сортировки - C++
нужно выполнить сортировку массива целых чисел 3 методами: простыми включениями, простым выбором, простым обменом подскажите пожалуйста...

Алгоритмы поиска - C++
Разработать проект, выполняющий и наглядно иллюстрирующий поиск наибольшего или наименьшего элемента в матрице размерности 5 * 5. На...

Циклические Алгоритмы - C++
Написать программу для вычисления значения функции y=cos(x), если значения аргумента x меняются в интервале от 0 до 5 с шагом 0,2. ...

Циклические алгоритмы. - C++
Циклические алгоритмы. 1. Известны оценки по информатике каждого из 20 учеников класса. Сколько учеников имеют по информатике оценку...

Алгоритмы сортировок - C++
Добрый день. Если у кого есть, просьба выложить коды следующих сортировок: Пирамидальная сортировка. Сортировка подсчетом Простое...

Итерационные алгоритмы - C++
Помогите пожалуйста с заданием нужно решить на основе реккурентных отношений

Алгоритмы сжатия - C++
Доброго всем времени суток. Интересует такой вопрос. Можете посоветовать какую-нибудь подробную литературу по алгоритмам сжатия данных на...

Алгоритмы и методы - C++
Надо записать на С++(желательно Borland 5.02) алгоритмы и методы: 1.Алгоритм разделенных корней 2.Метод простых итераций 3.Метод...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
22457 / 10862 / 1769
Регистрация: 12.02.2012
Сообщений: 17,989
09.06.2013, 09:54     Алгоритмы на графах #2
мне кажется, здесь проще поступить так:
0) обнулить число штатов
1) из номеров дорог построить матрицу смежности;
2) из первого еще не посещенного города выполнить обход графа (в глубину или ширину - неважно);
3) увеличить число штатов на 1
4) проверить, есть ли непосещенные города
4a) нет - вывести число штатов -> конец
4b) да - на п. 2
Yandex
Объявления
09.06.2013, 09:54     Алгоритмы на графах
Ответ Создать тему
Опции темы

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