Задача №3559. Алгоритм Краскала
Напишите программу, которая будет либо находить вес ОДМВ (остовного дерева минимального веса) неориентированного взвешенного графа без петель с положительными длинами ребер, либо устанавливать, что введённый граф несвязный.
Первая строка входных данных содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них разные, в пределах от 0 до N–1 каждое, и обозначают концы соответствующего ребра, третье — в пределах от 1 до 1000000000 и обозначает длину этого ребра. Гарантировано, что все ребра имеют различные длины. Количество вершин графа не превышает 80000, количество рёбер — 100000.
Выведите на стандартный выход (экран) либо единственное число — сумму длин рёбер остовного дерева минимального веса (если граф связный), либо единственную фразу «NON-CONNECTED» (без кавычек, через дефис) если граф не связный.
При указанных ограничениях на длины и количество ребер возможно переполнение типа int, используйте long long.
Указания.
Алгоритму Краскала, в отличие от предыдущих графовых задач, совершенно не нужно, чтобы граф был представлен списками смежности. Зато нужно сортировать ребра по длине. Разрешается самому написать сортировки (со сложностью O(N logN), иначе программа окажется не достаточно эффективной). Но рекомендуется заставить работать стандартный алгоритм sort. Для него нужно подключить заголовочный файл algorithm и указать, каким образом сравнивать структуры, представляющие ребра. Для этого можно перегрузить (overload) операцию сравнения operator < для типа, представляющего ребро (подробнее см. в книгах, help-е, а также в указаниях к задаче «Алгоритм Дейкстры за M logN»).
5 7 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10
19