מימוש (חלק 1)

שיעור 5 מתוך 9 בקורס מיון טופולוגי – אלגוריתמים על גרפים של Coddy.

נתחיל בדרגות כניסה, לבו של האלגוריתם של Kahn.

אתגר

קל

המנוע של האלגוריתם של Kahn הוא דרגת הכניסה של כל קודקוד. בואו נחשב אותה תחילה.

כתבו פונקציה בשם inDegrees שמקבלת את n ואת מערך edges השטוח (זוגות מכוונים u -> v), ומחזירה מערך שבו המיקום v הוא מספר הקשתות המצביעות אל הקודקוד v.

לדוגמה, inDegrees(4, [0,1, 0,2, 1,3, 2,3]) מחזירה [0, 1, 1, 2].

נסו בעצמכם

#include <stdlib.h>

int* inDegrees(int n, int* edges, int edges_size, int* returnSize) {
    // כתבו כאן את הקוד
    *returnSize = 0;
    return edges;
}