Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Странная сеть

 В одной из самых крупных IT-компаний Беларуси уже много лет действует локальная сеть, в которую входят N компьютеров, последовательно пронумерованных целыми числами от 1 до N. Для соединения компьютеров используется провод специального типа. С помощью одного провода можно напрямую соединить ровно два компьютера, причем соединение позволяет передавать данные в двух направлениях. Каждый компьютер имеет два порта, поэтому он может быть соединен напрямую не более чем с двумя другими компьютерами. Сеть организована таким образом, что если два компьютера не соединены напрямую проводом, то передача данных может осуществляться  через промежуточные компьютеры. Путем передачи данных между компьютерами с номерами V1 и VK называется такая последовательность компьютеров V1, V2, … , VK-1, VK, что для любого 2 iK существует прямое соединение между компьютерами Vi-1 и ViДлиной пути передачи данных считается количество используемых промежуточных компьютеров. Минимальным путем передачи данных между компьютерами Vi и Vj является такой путь передачи данных, длина которого минимальна из возможных.

Для приведенного ниже примера длина минимального пути передачи данных между компьютерами 1 и 8 равна 2, а между компьютерами 2 и 7 равна 1, между компьютерами 2 и 4 равна 0.   

рисунок 1

Если не существует ни одного пути передачи данных между какими-либо двумя компьютерами, то в данном случае длина минимального пути передачи данных между этими компьютерами считается равной нулю. Для приведенного выше примера между компьютерами 1 и 4 не существует пути передачи данных, поэтому длина минимального пути передачи данных равна 0.

Для выяснения эффективности локальной сети необходимо определить коэффициент связности, значение которого равно сумме длин минимальных путей передачи данных между всеми парами компьютеров. Пары, отличающиеся порядком следования элементов считаются различными, то есть пара (1, 2) и (2, 1) считаются различными.

Вашей задачей является определить значение коэффициента связности для заданной локальной сети. 

Входные данные:

 Первая строка входного файла  содержит два целых числа N и M – число компьютеров и число прямых соединений соответственно  (2 ≤ N ≤ 105 ,  1 ≤ M ≤ 106). Числа разделены одиночным  пробелом.

Каждая из следующих M строк содержит описание одного прямого соединения. Каждое прямое соединение описывается при помощи  двух целых чисел Xi и Yi  (1 ≤ Xi, YiN; XiYi), разделенных пробелом – номера соответствующих компьютеров, соединенных напрямую. Известно, что XiXj или YiYj, если ij.  Строки в файле нумеруются последовательно, начиная с единицы.

Выходные данные:

 Единственная строка выходного файла должна содержать одно целое число – коэффициент связности локальной сети.


Примеры:
input.txt output.txt
1 2 1
1 2
0
2 8 7
1 3
3 6
4 2
7 4
2 5
5 7
6 8
12

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 25, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]