Count reachable vertices (DFS)

Challenge

int dfs_reachable_count(const int *adj,int n,int src);

Return how many vertices are reachable from src, including src itself, following directed edges.

Input format

adj n×n directed; 0<=src<n.

Output format

Reachable vertex count (≥1).

Constraints

Use a visited array to avoid infinite loops on cycles.

Starter code

#include <stddef.h>
/* Number of nodes reachable from `start` (including start) via DFS in the directed adjacency matrix. */
int dfs_reachable_count(const int *adj,int n,int start){ (void)adj;(void)n;(void)start; return 0; }

Common mistakes

Forgetting to mark visited before recursing → infinite loop on a cycle.

Edge cases to handle

src with no out-edges → 1; fully connected → n.

Background lessons

• Depth-first search