是否为二分图
Coddy 图：数据结构系列 #9 课程的第 14 课，共 14 课。
如果你能把图的顶点分成两组，并且每条边都连接一组中的一个顶点和另一组中的一个顶点，那么这个图就是二分图。可以把两组想成红色和蓝色：每条边的两个端点一个是红色，一个是蓝色。
BFS 可以用来简洁地判断。从任意顶点开始，把它染成红色，然后向外遍历。每个新邻居都染成与当前顶点相反的颜色。如果我们发现一条边连接了两个相同颜色的顶点，那么这个图就不是二分图。典型的反例是奇数长度的环：三角形 0-1-2-0 会迫使顶点 0 同时是红色和蓝色。
有一点要记住：如果图有多个连通分量，你必须在每个分量中重新开始 2-着色。最简单的模式是用一个循环遍历所有顶点，每当发现一个尚未着色的顶点时，就启动一次 BFS。
挑战
简单编写一个函数 isBipartite，接收一个二维 int 数组 adjacency 和一个 int 数组 vertices。如果图是二分图，则返回 true，否则返回 false。
构建图（对每个顶点调用 addVertex，然后对每条边调用 addEdge）。接着使用 BFS 遍历每个连通分量，并进行二染色：将起始顶点的颜色设为 0，将每个邻居的颜色设为 1 - color[u]。如果发现一条边的两个端点已有相同颜色，则返回 false。否则返回 true。
你必须使用 Graph 类（在 graph 中提供），不要使用语言内置类型（映射、集合）来表示邻接关系。算法的辅助数据（颜色映射、队列）可以使用标准库类型。
亲手试试
#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;
}
图：数据结构系列 #9中的所有课
自己练习： C 在线编译器