Implementation (Part 1)
Урок 5 из 9 курса Алгоритм Краскала — Алгоритмы на графах на Coddy.
Мы начнем с union-find, механизма обнаружения циклов.
Задание
СреднеПроверка циклов в алгоритме Краскала основана на системе непересекающихся множеств (union-find). Давайте сначала реализуем её, используя её для подсчета компонент связности.
Напишите функцию с именем countSets, которая принимает n и плоский массив edges (тройки [u, v, w, ...], неориентированные; здесь веса игнорируйте) и возвращает количество компонент связности, вычисленное с помощью union-find.
Например, для 4 вершин и ребер [0,1,5, 2,3,5] есть 2 компоненты: {0,1} и {2,3}.
Попробуйте сами
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Напишите код здесь
return 0;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Алгоритм Краскала — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity