Implementacja (część 1)
Lekcja 5 z 9 w kursie Algorytm Kruskala — algorytmy grafowe w Coddy.
Zaczynamy od struktury union-find, silnika wykrywania cykli.
Wyzwanie
ŚredniTest cykli Kruskala opiera się na strukturze union-find. Najpierw ją zbudujmy i użyjmy do policzenia składowych spójnych.
Napisz funkcję o nazwie countSets, która przyjmuje n oraz płaską tablicę edges (trójki [u, v, w, ...], graf nieskierowany; wagi na razie zignoruj) i zwraca liczbę składowych spójnych obliczoną za pomocą struktury union-find.
Na przykład dla 4 wierzchołków i krawędzi [0,1,5, 2,3,5] są 2 składowe: {0,1} i {2,3}.
Spróbuj swoich sił
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Napisz tutaj kod
return 0;
}
Sprawdź sięTa lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.
Wszystkie lekcje w sekcji Algorytm Kruskala — algorytmy grafowe
2Algorytm
Jak to działa?PseudokodImplementacja (część 1)Implementacja (część 2)
Złożoność czasowa i pamięciowaPoćwicz samodzielnie: Kompilator C online