Contar componentes conexas
Lección 13 de 14 del curso Grafos - Serie de Estructuras de Datos #9 de Coddy.
Un componente conexo es un conjunto maximal de vértices donde cada par tiene un camino entre ellos. Un grafo sin aristas tiene tantos componentes como vértices; uno totalmente conexo tiene exactamente un componente.
Para contarlos, recorre todos los vértices. Cada vez que encuentres uno que aún no haya sido visitado, ese es un nuevo componente: incrementa el contador, luego realiza un BFS o DFS desde él para marcar cada vértice alcanzable como visitado. Continúa con el siguiente vértice no visitado.
Este desafío te da TANTO la lista de vértices como las aristas, porque los vértices aislados (sin aristas) siguen contando como su propio componente y necesitamos saber que existen.
Desafío
FácilEscribe una función countConnectedComponents que reciba un arreglo bidimensional de enteros adjacency y un arreglo de enteros vertices, y devuelva el número de componentes conectados en el grafo.
Construye el grafo: primero aplica addVertex en cada clave de vertices (para que los vértices aislados estén presentes), luego aplica addEdge en cada par de adjacency. Después, recorre todos los vértices: cada uno que no haya sido visitado inicia un nuevo componente (incrementa el contador), luego realiza un DFS/BFS desde él para marcar todo su componente como visitado.
Debes usar la clase Graph (proporcionada en graph); no utilices elementos integrados del lenguaje (mapas, conjuntos) para modelar la adyacencia. Los datos auxiliares para el algoritmo (conjuntos de visitados, pilas) pueden usar tipos de la biblioteca estándar (stdlib).
Pruébalo tú mismo
#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;
}