Is Bipartite
Lesson 14 of 14 in Coddy's Graphs - Data Structures Series #9 course.
A graph is bipartite if you can split its vertices into two groups so that every edge connects a vertex in one group to a vertex in the other. Think red and blue: every edge has one red endpoint and one blue endpoint.
BFS gives a clean test. Start at any vertex, color it red, and walk outward. Each new neighbor gets the opposite color of the vertex we came from. If we ever see an edge that connects two vertices with the same color, the graph is not bipartite. The classic offender is an odd-length cycle: a triangle 0-1-2-0 forces vertex 0 to be both red and blue.
One thing to remember: if the graph has multiple connected components, you have to start a fresh 2-coloring on each one. The easiest pattern is a single loop over all vertices that kicks off a BFS whenever it finds an uncolored vertex.
Challenge
EasyWrite a function isBipartite that gets a 2D int array adjacency and an int array vertices, and returns true if the graph is bipartite, false otherwise.
Build the graph (addVertex each, then addEdge each). Then 2-color via BFS over every connected component: assign the start color 0, give each neighbor color 1 - color[u]. If you ever find an edge where both endpoints already have the same color, return false. Otherwise return true.
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 (color map, queue) 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("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}