Is the graph bipartite?

Challenge

For an undirected graph (symmetric adj):

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

Return 1 if the graph is 2-colorable (bipartite), else 0. Disconnected graphs must check every component.

Input format

adj n×n symmetric 0/1.

Output format

1 if bipartite, else 0.

Constraints

—

Starter code

#include <stddef.h>
/* Return 1 if the UNDIRECTED graph (symmetric adjacency matrix) is bipartite (2-colorable), else 0. */
int is_bipartite(const int *adj,int n){ (void)adj;(void)n; return 1; }

Common mistakes

Only checking one component; a graph is bipartite only if all components are.

Edge cases to handle

No edges → 1; any odd cycle → 0.

Background lessons

• Bipartite graphs