Sfida finale #1

Lezione 8 di 9 del corso Ricerca in profondità - Algoritmi su grafi di Coddy.

Sfida

Medio

È il momento di usare DFS per rispondere a una domanda sull'intero grafo.

Scrivi una funzione chiamata countComponents che prende n e l'array piatto edges (non orientato) e restituisce il numero di componenti connesse (parti separate) nel grafo.

Ad esempio, con 5 vertici e gli archi [0,1, 0,2, 3,4] ci sono 2 componenti: {0,1,2} e {3,4}.

Provalo tu

#include <stdlib.h>

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

Tutte le lezioni di Ricerca in profondità - Algoritmi su 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