Sfida finale #1

Lezione 8 di 9 del corso Ordinamento topologico - Algoritmi sui grafi di Coddy.

Sfida

Medio

L'algoritmo di Kahn funge anche da rilevatore di cicli.

Scrivi una funzione chiamata hasCycle che accetta n e l'array piatto edges (diretto) e restituisce 1 se il grafo contiene un ciclo, oppure 0 se è aciclico.

Suggerimento: esegui l'algoritmo di Kahn. Se riesce a disporre tutti gli n vertici, il grafo è aciclico; se si blocca lasciando dei vertici, c'è un ciclo.

Provalo tu

#include <stdlib.h>

int hasCycle(int n, int* edges, int edges_size) {
    // Scrivi il codice qui
    return 0;
}

Tutte le lezioni di Ordinamento topologico - Algoritmi sui grafi

1Introduzione

Introduzione Motivazione

2L'algoritmo

Come funziona?Pseudocodice Implementazione (Parte 1)Implementazione (Parte 2)

Complessità temporale e spaziale

3Sfide finali

Sfida finale #1Sfida finale #2

Esercitati da solo: Compilatore C online