Лабораторные. Кузовлева

1 работа

Построить минимальный остов связного неориентированного взвешенного графа.

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

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

Пример

       (5)
     1 ---- 2      4
(15) |      |(0)   | (25)
     +----- 3 -----+

4
2 5 3 15 0
1 5 3 0 0
1 15 2 0 4 25 0
3 25 0

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

Граф, заданный массивом смежности.

N - количество вершин в графе.

Далее последовательно расположены списки смежностей для каждой вершины. Список заканчивается 0.

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

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

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