Is the graph connected?

Challenge

int is_connected(const int *adj,int n);

Return 1 if the undirected graph is connected (every vertex reachable from any one), else 0.

Input format

adj n×n symmetric 0/1.

Output format

1 if connected, else 0.

Constraints

n<=1 is connected.

Starter code

#include <stddef.h>
/* Return 1 if the UNDIRECTED graph (symmetric adjacency matrix) is connected (all nodes reachable from any one), else 0. */
int is_connected(const int *adj,int n){ (void)adj;(void)n; return 1; }

Common mistakes

Starting DFS from every vertex (unneeded) — one traversal suffices.

Edge cases to handle

Single vertex → 1; an isolated vertex → 0.

Background lessons

• Minimum spanning trees