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

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

Войти
Регистрация
Восстановить пароль
 
sm1992
2 / 2 / 0
Регистрация: 27.05.2013
Сообщений: 8
#1

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

28.05.2013, 21:04. Просмотров 225. Ответов 0
Метки нет (Все метки)

Входной файл: 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     Необходимо узнать, кого с кем нужно дознакомить минимальное количество раз, чтобы все стали друзьями из одной "тусовоки"
Посмотрите здесь:

Найти минимальное количество шариков, которое необходимо перекрасить, чтобы все шарики были одного цвета - C++
Написал код для одной задачи. Ответ выдает он вроде правильный. Но на сайте при тестировании моего алгоритма, он проходит тест на 31%...

Минимальное число монеток, которые нужно перевернуть, чтобы все были повернуты вверх одной стороной - C++
Добрый вечер, наткнулся на простую задачу - сложность всего лишь 8%. Её нужно решить с использованием цикла for. Задачу, я, конечно, решил,...

В чём ошибка? Надо чтобы подсчитывалось сколько раз нажата цифра "1" - C++
#include <iostream> #include <conio.h> #include <stdio.h> int main() { int c,i; int v; for(i=0; i<11;i++) ...

Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n гривен - C++
В банкомате имеются в достаточном количестве купюры номиналом 10, 20, 50, 100, 200 и 500 гривен. Найти минимальное количество купюр,...

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

Создать класс "Множество строк" (нужно чтобы элементы не повторялись) - C++
Подскажите, как создать класс множество строк( нужно чтоб элементы не повторялись) ? Нужно также реализовать добавления и удаление...

Нужно чтобы программа нарисовала MMD или ММД с помощью "*" - C++
Нужно чтобы программа нарисовала MMD или ММД с помощью "*". Пользователю предоставляется выбор алфавита. Пожалуйста помогите. // MMD...

Подсчитать сумму "серых" элементов, а "черные" сложить только один раз - C++
Помогите с заданием, нужно подсчитать сумму "серых" элементов, а "черные" сложить только один раз, чтобы не было двум одинаковых сумм. ...

Строка: Имеются четыре буквы, необходимо удалить из массива все символы, кроме этих четырех и "склеить" оставшееся в непрерывный символьный массив. - C++
Имеются четыре буквы, необходимо удалить из массива все символы, кроме этих четырех и "склеить" оставшееся в непрерывный символьный...

Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром - C++
Здравствуйте, помогите пожалуйсто, был бы очень признателен хотя бы за идею решения(поидеи методом ветвей и границ она решается) ...


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

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

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