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

Определить, является ли система магистралей чётно-нечётной или нет - C++

Восстановить пароль Регистрация
 
Stasq329
0 / 0 / 0
Регистрация: 01.05.2014
Сообщений: 15
15.05.2014, 01:05     Определить, является ли система магистралей чётно-нечётной или нет #1
Условие
Предположим, что есть страна с N городами. Дана система магистралей, соединяющая напрямую города между собой. Движение по магистрали возможно в обе стороны. Длина любого прямого соединения равна 1.

Для того, чтобы система магистралей называлась чётно-нечётной, необходимо, чтобы каждая пара различных городов была соединена маршрутом как чётной длины, так и нёчетной длины (причём маршрут обязательно должен существовать, кроме того, от маршрута не требуется, чтобы он был простым).

Необходимо определить, является ли система магистралей чётно-нечётной или нет. Если ответ на вопрос отрицательный, то найти одно из подмножеств множества городов, в котором максимальное количество элементов и которое удовлетворяет следующему условию: если какие-либо два различных города из этого подмножества и соединены маршрутом, то его длина чётна.

Входные данные
Входные данные находятся в файле input.txt.

Первая строка содержит число городов N (N ≤ 300).
Следующие N строк файла задают магистрали: (i + 1)-я строка файла содержит номера городов, которые связаны напрямую с городом i (если таких городов нет, то строка содержит ноль; числа в строке разделены пробелами).
Выходные данные
Выходные данные находятся в файле output.txt.
Если система магистралей является чётно-нечётной, то файл содержит единственную строку YES.
Если нет, то первая строка содержит сообщение NO, а вторая строка содержит мощность одного из максимальных по мощности подмножеств X.

Пример 1
input.txt
5
2 5
3 1
2 4
3 5
4 1
output.txt
YES
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2014, 01:05     Определить, является ли система магистралей чётно-нечётной или нет
Посмотрите здесь:

как проверить число на то, является ли оно им или нет C++
C++ Проверить, является ли последовательность прогрессией или нет?
While. Определить, является ли натуральное N (вводить с клавиатуры) степенью числа 4 или нет C++
Напишите функцию bool IsDigit(unsigned char c), определяющую, является ли данный символ цифрой или нет C++
C++ Дана строка. На печать выдать слова нечётной длины, в которых нет одинаковых букв
На печать выдать слова нечётной длины, в которых нет одинаковых C++
C++ Определить, является введенная буква гласной или согласной
Проверка является ли строка числом полностью числом или нет? C++

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

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

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