Conta le componenti connesse
Lezione 13 di 14 del corso Grafi - Serie sulle strutture dati #9 di Coddy.
Una componente connessa è un insieme massimale di vertici in cui ogni coppia è collegata da un percorso. Un grafo senza archi ha tanti componenti quanti sono i suoi vertici; un grafo completamente connesso ha esattamente un componente.
Per contarli, visita tutti i vertici. Ogni volta che ne trovi uno non ancora visitato, è un nuovo componente: incrementa il contatore, poi esegui BFS o DFS a partire da esso per contrassegnare come visitati tutti i vertici raggiungibili. Continua con il vertice successivo non visitato.
Questa sfida ti fornisce SIA l'elenco dei vertici SIA gli archi, perché i vertici isolati (senza archi) contano comunque come componenti a sé stanti e dobbiamo sapere che esistono.
Sfida
FacileScrivi una funzione countConnectedComponents che riceva un array di interi bidimensionale adjacency e un array di interi vertices, e restituisca il numero di componenti connesse nel grafo.
Costruisci il grafo: prima chiama addVertex per ogni chiave in vertices (così sono presenti anche i vertici isolati), poi chiama addEdge per ogni coppia in adjacency. Quindi visita tutti i vertici: ogni vertice non visitato avvia una nuova componente (incrementa il contatore), poi esegui una DFS/BFS a partire da esso per contrassegnare come visitata l’intera componente.
Devi usare la classe Graph (fornita in graph): non usare le strutture integrate nel linguaggio (mappe, insiemi) per rappresentare l’adiacenza. I dati ausiliari per l’algoritmo (insiemi dei vertici visitati, pile) possono usare i tipi della libreria standard.
Provalo tu
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}
Tutte le lezioni di Grafi - Serie sulle strutture dati #9
Esercitati da solo: Compilatore C online