[LeetCode]Is Graph Bipartite?

判断二分图的问题，所谓二分图，指的是顶点可以分成两个不相交的集合U和V，使得所有的边的两个端点分别位于集合U和V中。也就是说，如果我们把所有边的一个端点图上红色，另一个端点一定可以全涂成蓝色且不会和之前的红色有冲突。我们只需要去验证这一点即可，从任意点开始，假设其涂为红色，那么相邻的所有点都涂为蓝色，蓝色的所有相邻点涂为红色，依次类推，我们用dfs或者bfs即可验证。最后需要注意的是图可能不是connected的，所以对于所有connected component我们都需要验证。时间复杂度O(V + E)，空间复杂度O(V)，代码如下：

dfs：



bfs: