Compter les composantes connexes
Leçon 13 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Une composante connexe est un ensemble maximal de sommets où chaque paire possède un chemin entre eux. Un graphe sans arêtes possède autant de composantes qu'il a de sommets ; un graphe entièrement connexe possède exactement une composante.
Pour les compter, parcourez tous les sommets. Chaque fois que vous en trouvez un qui n'a pas encore été visité, il s'agit d'une nouvelle composante : incrémentez le compteur, puis effectuez un BFS ou un DFS à partir de celui-ci pour marquer chaque sommet atteignable comme visité. Continuez avec le sommet non visité suivant.
Ce défi vous donne À LA FOIS la liste des sommets et les arêtes, car les sommets isolés (sans arêtes) comptent toujours comme leur propre composante et nous devons savoir qu'ils existent.
Défi
FacileÉcrivez une fonction countConnectedComponents qui reçoit un tableau d'entiers 2D adjacency et un tableau d'entiers vertices, et renvoie le nombre de composantes connexes dans le graphe.
Construisez le graphe : d'abord addVertex sur chaque clé dans vertices (pour que les sommets isolés soient présents), puis addEdge sur chaque paire dans adjacency. Parcourez ensuite tous les sommets : chaque sommet non visité commence une nouvelle composante (incrémentez le compteur), puis effectuez un DFS/BFS à partir de celui-ci pour marquer toute sa composante comme visitée.
Vous devez utiliser la classe Graph (fournie dans graph) - n'utilisez pas les types intégrés du langage (maps, sets) pour modéliser l'adjacence. Les données auxiliaires pour l'algorithme (ensembles de sommets visités, piles) peuvent utiliser les types de la bibliothèque standard (stdlib).
Essayez vous-même
#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;
}