Задача №3560. Алгоритм Краскала с восстановлением дерева
Задача отличается от задачи «Алгоритм Краскала» исключительно тем, что в случае связности начального графа просят вывести более подробный ответ: не только суммарный вес минимального остовного дерева, а и само дерево как граф.
Напишите программу, которая будет либо находить ОДМВ (остовное дерево минимального веса) неориентированного взвешенного графа без петель с положительными длинами ребер, либо устанавливать, что введённый граф несвязный.
Первая строка входных данных содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них разные, в пределах от 0 до N–1 каждое, и обозначают концы соответствующего ребра, третье — в пределах от 1 до 1000000000 и обозначает длину этого ребра. Гарантировано, что все ребра имеют различные длины. Количество вершин графа не превышает 80000, количество рёбер — 100000.
Если заданный во входных данных граф не связный, следует вывести на стандартный выход (экран) единственную фразу «NON-CONNECTED» (без кавычек, через дефис). Если связный, то надо вывести в первой строке единственное число — сумму длин рёбер найденного остовного дерева минимального веса, а в дальнейших N строках само дерево как граф, представленный списками смежности (сначала список для 0-й вершины, потом для 1-й, и так до (N–1)-й). Каждая строка должна содержать: номер очередной вершины, пробел, двоеточие, пробел, перечень всех рёбер, исходящих из данной вершины. Каждое ребро должно описываться номером вершины, куда оно идёт, открывающей круглой скобкой (без пробела перед ней), весом этого ребра и закрывающей круглой скобкой. Между записями разных рёбер, исходящих из одной вершины, должны быть запятая и пробел. Перечень рёбер, исходящих из одной вершины, должен быть упорядочен по возрастанию номеров вершин, куда идут эти рёбра. После описания последнего ребра строка должна заканчиваться символом перевода строки (ни запятой, ни пробела).
Поскольку во входных данных гарантируется, что все рёбра начального графа имеют различные веса, а в формате вывода результата требуется определённый порядок, ответ однозначен.
5 7 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10
19 0 : 4(10) 1 : 3(2) 2 : 3(4), 4(3) 3 : 1(2), 2(4) 4 : 0(10), 2(3)
100 1 17 42 111
NON-CONNECTED