Implementation (Part 1)
Lição 5 de 9 do curso Algoritmo de Kruskal - Algoritmos de Grafos da Coddy.
Começamos com o union-find, o mecanismo de detecção de ciclos.
Desafio
MédioO teste de ciclo de Kruskal baseia-se em union-find. Vamos construir isso primeiro, usando-o para contar componentes conectados.
Escreva uma função chamada countSets que recebe n e o array linear edges (triplas [u, v, w, ...], não direcionadas; ignore os pesos aqui) e retorna o número de componentes conectados, computado com union-find.
Por exemplo, com 4 vértices e arestas [0,1,5, 2,3,5] existem 2 componentes: {0,1} e {2,3}.
Experimente você mesmo
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Escreva o código aqui
return 0;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Kruskal - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity