Contar Componentes Conectados
Lição 13 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.
Um componente conectado é um conjunto maximal de vértices onde cada par possui um caminho entre eles. Um grafo sem arestas tem tantos componentes quanto vértices; um totalmente conectado tem exatamente um componente.
Para contá-los, percorra todos os vértices. Sempre que encontrar um que ainda não foi visitado, esse é um novo componente: incremente o contador, então realize uma BFS ou DFS a partir dele para marcar cada vértice alcançável como visitado. Continue com o próximo vértice não visitado.
Este desafio fornece TANTO a lista de vértices quanto as arestas, porque vértices isolados (sem arestas) ainda contam como seu próprio componente e precisamos saber que eles existem.
Desafio
FácilEscreva uma função countConnectedComponents que recebe um array de inteiros 2D adjacency e um array de inteiros vertices, e retorna o número de componentes conectados no grafo.
Construa o grafo: primeiro use addVertex em cada chave em vertices (para que os vértices isolados estejam presentes), depois use addEdge em cada par em adjacency. Em seguida, percorra todos os vértices: cada um não visitado inicia um novo componente (incremente o contador) e, em seguida, realize um DFS/BFS a partir dele para marcar todo o seu componente como visitado.
Você deve usar a classe Graph (fornecida em graph) - não use recursos integrados da linguagem (mapas, conjuntos) para modelar a adjacência. Dados auxiliares para o algoritmo (conjuntos de visitados, pilhas) podem usar tipos da biblioteca padrão (stdlib).
Experimente você mesmo
#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;
}