1、思路

• 对图中每一个点着色，相邻的点着不同颜色，若能够成功对所有点着色，则该图是二分图，否则不是；

• 用一个colors数组保存每个点的颜色，元素初始化为-1表示未上色，0和1表示两种不同的颜色；

• 时间复杂度与空间复杂度均为 $O(N)$。

2、BFS解法

class Solution {
public:
    //对当前元素及其可达的元素上色
    bool setColor(vector<vector<int>>& graph, vector<int>& colors, int i, int color)
    {
        colors[i] = color;

        queue<int> q;
        q.push(i);

        while (!q.empty())
        {
            int v = q.front();
            q.pop();

            for (int neighbor : graph[v])       //遍历当前元素的相邻元素
            {
                if (colors[neighbor] >= 0)      //若该相邻元素已经上色
                {
                    if (colors[neighbor] == colors[v])
                    {
                        return false;           //同色返回false
                    }
                }
                else                            //上不同颜色
                {
                    q.push(neighbor);
                    colors[neighbor] = 1 - colors[v];
                }
            }
        }

        return true;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, -1);              //初始化为-1，表示未上色

        for (int i = 0; i < n; ++ i)
        {
            if (colors[i] == -1)                //对每一个未上色的元素上色
            {
                if (!setColor(graph, colors, i, 0))
                {
                    return false;
                }
            }
        }

        return true;
    }
};

3、DFS递归解法

class Solution {
public:
    bool setColor(vector<vector<int>>& graph, vector<int>& colors, int i, int color)
    {
        if (colors[i] >= 0)
        {
            return colors[i] == color;
        }

        colors[i] = color;

        for (int neighbor : graph[i])
        {
            if (!setColor(graph, colors, neighbor, 1 - colors[i]))
            {
                return false;
            }
        }

        return true;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors(n, -1);

        for (int i = 0; i < n; ++ i)
        {
            if (colors[i] == -1)
            {
                if (!setColor(graph, colors, i, 0))
                {
                    return false;
                }
            }
        }

        return true;
    }
};