Końcowe wyzwanie nr 1

Lekcja 8 z 9 w kursie Sortowanie topologiczne – algorytmy grafowe w Coddy.

Wyzwanie

Średni

Algorytm Kahna może również służyć do wykrywania cykli.

Napisz funkcję o nazwie hasCycle, która przyjmuje n i płaską tablicę edges (skierowaną) i zwraca 1, jeśli graf zawiera cykl, lub 0, jeśli jest acykliczny.

Podpowiedź: uruchom algorytm Kahna. Jeśli uda mu się umieścić wszystkie n wierzchołków, graf jest acykliczny; jeśli utknie, gdy pozostaną jeszcze wierzchołki, oznacza to, że istnieje cykl.

Spróbuj swoich sił

#include <stdlib.h>

int hasCycle(int n, int* edges, int edges_size) {
    // Wpisz tutaj kod
    return 0;
}

Wszystkie lekcje w sekcji Sortowanie topologiczne – algorytmy grafowe

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

Jak to działa?Pseudokod Implementacja (część 1)Implementacja (część 2)

Złożoność czasowa i pamięciowa

3Końcowe wyzwania

Końcowe wyzwanie nr 1Końcowe wyzwanie nr 2

Poćwicz samodzielnie: Kompilator C online