Implementation (Part 1)
Leçon 5 sur 9 du cours Algorithme de Kruskal - Algorithmes de graphes de Coddy.
Nous commençons par union-find, le moteur de détection de cycles.
Défi
MoyenLe test de cycle de Kruskal repose sur l'union-find. Commençons par construire cela, en l'utilisant pour compter les composantes connexes.
Écrivez une fonction nommée countSets qui prend n et le tableau plat edges (triplets [u, v, w, ...], non orientés ; ignorez les poids ici) et renvoie le nombre de composantes connexes, calculé avec union-find.
Par exemple, avec 4 sommets et les arêtes [0,1,5, 2,3,5], il y a 2 composantes : {0,1} et {2,3}.
Essayez vous-même
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Écrire le code ici
return 0;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Kruskal - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity