DFS
O(N + M)
通常在二分图的上下文中,会使用 颜色 顶点的概念。将图形分成两部分称为 着色 其顶点具有两种不同的颜色。每条边必须连接不同颜色的顶点。 DFS.
我们从任意顶点开始绘制,我们用任意颜色绘制。 当沿着每条边通过时,用相反的颜色绘制下一个顶点。 如果在迭代相邻顶点时,我们发现一个顶点已经被涂上了与当前顶点相同的颜色,那么图中存在一个奇数循环,这意味着它不是二分的。