Implementation (Part 1)
Lección 5 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
Comenzamos con union-find, el motor de detección de ciclos.
Desafío
IntermedioLa prueba de ciclos de Kruskal se basa en union-find. Vamos a construir eso primero, utilizándolo para contar los componentes conectados.
Escribe una función llamada countSets que reciba n y el array plano edges (triples [u, v, w, ...], no dirigidos; ignora los pesos aquí) y devuelva el número de componentes conectados, calculados con union-find.
Por ejemplo, con 4 vértices y las aristas [0,1,5, 2,3,5] hay 2 componentes: {0,1} y {2,3}.
Pruébalo tú mismo
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Escribe el código aquí
return 0;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Kruskal - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity