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

Необходимо узнать, кого с кем нужно дознакомить минимальное количество раз, чтобы все стали друзьями из одной "тусовоки" - C++

Восстановить пароль Регистрация
 
sm1992
2 / 2 / 0
Регистрация: 27.05.2013
Сообщений: 8
28.05.2013, 21:04     Необходимо узнать, кого с кем нужно дознакомить минимальное количество раз, чтобы все стали друзьями из одной "тусовоки" #1
Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 1 секунда
На посвящение в студенты собрались все первокурсники. Некоторые из них знают друг друга. Считается, что два незнакомых человека тоже друзья, если у них есть какой-нибудь общий друг. Группа студентов, которые больше ни с кем не знакомы, называется "тусовкой". Студенты из различных "тусовок" не имеют общих знакомых. Необходимо узнать, кого с кем нужно дознакомить минимальное количество раз, чтобы все стали друзьями из одной "тусовоки".

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

В первой строке входного файла input.txt записано целое число N - количество первокурсников. Во второй строке входного файла input.txt записано целое число K - количество известных непосредственных знакомств. Далее в следующих K строках записано по паре целых чисел Ai и Bi через один пробел, означающих, что первокурсники с номерами Ai и Bi знакомы непосредственно. Ограничения на значения: 1≤N≤1000, 0≤K≤1000000, 1≤Ai≤N, 1≤Bi≤N, i=1..N. Гарантируется, что для предложенного набора данных результат всегда существует. Каждая строка заканчивается переходом на новую строку.
Формат выходного файла:

В первую строку выходного файла output.txt необходимо вывести без пробелов число - количество X необходимых дополнительных знакомств. Далее в следующих X строках необходимо вывести по паре чисел Ai и Bi через один пробел - номера людей, которых необходимо познакомить друг с другом.

Пример ввода:

4
3
1 2
1 3
2 4
Пример вывода:

0
Пример ввода:

4
2
1 2
2 4
Пример вывода:

1
2 3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2013, 21:04     Необходимо узнать, кого с кем нужно дознакомить минимальное количество раз, чтобы все стали друзьями из одной "тусовоки"
Посмотрите здесь:

Нужно чтобы программа нарисовала MMD или ММД с помощью "*" C++
C++ Написать программу,которая находит все слова,в которых буква "а" встречается больше чем один раз.
C++ Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен
C++ Игра "Жизнь"; Нужно, чтобы первое поколение задавалось оператором (с клавиатуры)
Найти минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета C++
C++ Нужно узнать алгоритм в "морской бой"
Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной C++
C++ В чём ошибка? Надо чтобы подсчитывалось сколько раз нажата цифра "1"

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

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

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