Implementasi (Bagian 1)
Pelajaran 5 dari 9 dalam kursus Algoritma Kruskal: Algoritma Graf di Coddy.
Kita mulai dengan union-find, mesin pendeteksi siklus.
Tantangan
SedangPengujian siklus Kruskal mengandalkan union-find. Mari kita bangun terlebih dahulu, lalu gunakan untuk menghitung komponen terhubung.
Tulis fungsi bernama countSets yang menerima n dan array edges datar (tripel [u, v, w, ...], tak berarah; abaikan bobotnya di sini), lalu mengembalikan jumlah komponen terhubung yang dihitung dengan union-find.
Contohnya, dengan 4 simpul dan sisi [0,1,5, 2,3,5], ada 2 komponen: {0,1} dan {2,3}.
Coba sendiri
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// Tulis kodemu di sini
return 0;
}
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Algoritma Kruskal: Algoritma Graf
2Algoritma
Bagaimana cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online