Count Connected Components
Lesson 13 of 14 in Coddy's Graphs - Data Structures Series #9 course.
A connected component is a maximal set of vertices where every pair has a path between them. A graph with no edges has as many components as it has vertices; a fully connected one has exactly one component.
To count them, walk all the vertices. Whenever you find one that has not been visited yet, that is a new component: bump the counter, then BFS or DFS out from it to mark every reachable vertex as visited. Continue with the next unvisited vertex.
This challenge gives you BOTH the vertex list and the edges, because isolated vertices (no edges) still count as their own component and we have to know they exist.
Challenge
EasyWrite a function countConnectedComponents that gets a 2D int array adjacency and an int array vertices, and returns the number of connected components in the graph.
Build the graph: first addVertex on every key in vertices (so isolated vertices are present), then addEdge on every pair in adjacency. Then walk all vertices: each unvisited one starts a new component (increment the counter), then DFS/BFS from it to mark its whole component as visited.
You must use the Graph class (provided in graph) - do not use language built-ins (maps, sets) to model the adjacency. Auxiliary data for the algorithm (visited sets, stacks) may use stdlib types.
Try it yourself
#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;
}