מימוש (חלק 1)
שיעור 5 מתוך 9 בקורס האלגוריתם של קרוסקל - אלגוריתמים בגרפים של Coddy.
נתחיל ב-union-find, מנגנון זיהוי המחזורים.
אתגר
בינוניבדיקת המעגל של Kruskal מסתמכת על איחוד-חיפוש. נבנה את זה תחילה ונשתמש בכך כדי לספור רכיבים קשירים.
כתבו פונקציה בשם countSets שמקבלת את n ואת מערך edges השטוח (שלשות [u, v, w, ...], לא מכוון; התעלמו מהמשקלים כאן) ומחזירה את מספר הרכיבים הקשירים, המחושב באמצעות איחוד-חיפוש.
לדוגמה, עם 4 קודקודים וקשתות [0,1,5, 2,3,5] יש 2 רכיבים: {0,1} ו-{2,3}.
נסו בעצמכם
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// כתבו כאן את הקוד
return 0;
}
בחנו את עצמכםהשיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.
כל השיעורים ביחידה האלגוריתם של קרוסקל - אלגוריתמים בגרפים
תרגלו בעצמכם: קומפיילר C אונליין