Лабораторные. Дерендеева

1 работа

Построить минимальное связывающее дерево заданного множества точек на плоскости в прямоугольной метрике (d(M,N)=|XM-XN|+|YM-YN|)

Метод решения

Алгоритм Борувки-Краскла.

Пример

5
1 2
3 6
-1 -2
4 4
3 10

Файл входных данных

Множество точек на плоскости, заданное парами координат (x,y).

N - количество точек. Далее построчно координаты точек.

Файл выходных данных

Минимальное связывающее дерево, заданное в виде списков смежностей.

Для каждой точки исходного множества указать порядковые номера точек, смежных с ней. Список начинать с новой строки, точки внутри списка упорядочить по возрастанию номеров. Каждый список заканчивается 0. В последней строке файла записать вес.

2 работа

Пусть {A1,…,An} - пpоизвольная последовательность множеств (необязательно непеpесекающихся).

Системой pазличных пpедставителей для {A1,…,An} называется последовательность попаpно pазличных элементов {a1,…,an} такая, что ai пpинадлежит Ai.

Найти систему pазличных пpедставителей для заданной последовательности множеств, если она существует.

Файл входных данных

Множества Ai являются наборами натуральных чисел.

Последовательность {A1,…,An} задана числом n - количество множеств, далее в каждой строке перечислены элементы очередного множества, множества заканчиваются нулем.

Файл выходных данных

Y и во второй строке система представителей a1 … an (натуральные числа разделенные пробелами) или N.