Лабораторные. Кузовлева
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