Implementazione (Parte 1)
Lezione 5 di 9 del corso Algoritmo di Kruskal - Algoritmi sui grafi di Coddy.
Iniziamo con union-find, il motore per il rilevamento dei cicli.
Sfida
MedioIl test dei cicli di Kruskal si basa su union-find. Iniziamo implementandolo, usandolo per contare le componenti connesse.
Scrivi una funzione chiamata countSets che accetta n e l'array piatto edges (terne [u, v, w, ...], non orientato; qui ignora i pesi) e restituisce il numero di componenti connesse, calcolato con union-find.
Per esempio, con 4 vertici e gli archi [0,1,5, 2,3,5] ci sono 2 componenti: {0,1} e {2,3}.
Provalo tu
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Write code here
return 0;
}
Mettiti alla provaQuesta lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.
Tutte le lezioni di Algoritmo di Kruskal - Algoritmi sui grafi
2L'algoritmo
Come funziona?PseudocodiceImplementazione (Parte 1)Implementazione (Parte 2)
Complessità temporale e spazialeEsercitati da solo: Compilatore C online