Implementation (Part 1)
Урок 5 из 9 курса Топологическая сортировка — алгоритмы на графах на Coddy.
Мы начинаем с входящих степеней — основы алгоритма Кана.
Задание
ЛегкоОсновой алгоритма Кана является полустепень захода каждой вершины. Давайте сначала вычислим её.
Напишите функцию с именем 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;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Топологическая сортировка — алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity