Опишите алгоритм Крускала.

Question

Белый Ягуар · Accepted Answer

О! как-раз задачка:)...Входные данные
Первая строка входных данных содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них разные, в пределах от 0 до N–1 каждое, и обозначают концы соответствующего ребра, третье — в пределах от 1 до 1000000000 и обозначает длину этого ребра. Гарантировано, что все ребра имеют различные длины. Количество вершин графа не превышает 80000, количество рёбер — 100000.

Выходные данные
Выведите на стандартный выход (экран) либо единственное число — сумму длин рёбер остовного дерева минимального веса (если граф связный), либо единственную фразу «NON-CONNECTED» (без кавычек, через дефис) если граф не связный.........

Andrey Grigoryev · Answer

Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его основным деревом минимального веса.

Tatiana Filimonova · Answer

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Антонина Завадская · Answer

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году

Олеха Олехин · Answer

Алгоритм Крускала (или алгоритм Краскала) — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 г

Надежда Петрова · Answer

может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

Татьяна Романенко · Answer

— алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа

Анатолий Кондратов · Answer

алгоритм хускарла знаю-достал меч, то обагри его кровью..

Кото-Пч-О-Ла · Answer

ну-ну...щаз полезу в сети...золотой алгоритм ловить)

Отвечалка · Answer

алгоритм крускала...ну...он такой...алгоритмичный...

Евгений Максимов · Answer

если к уму прибавить разум то облысеет голова

Светлана Харламова · Answer

А посерьезнее что- нибудь нельзя задать?

Евгений Белов · Answer

не имею о нём представления

Наталья Нейбергер · Answer

Я таких и словов не знаю)))

Алена Вишневская · Answer

понятия не имею что это

Ирина Коваленко · Answer

в какие дебри ты зашел!

Юрий Васяня · Answer

НЕМОГУ