题解 | 判断二分图

题干分析：

题设给予我们与每个节点直接相连的节点组成的类邻接链表（数组实现），要求我们判断这是否为一个二分图

算法思路：

对图进行DFS二色涂色，如果能够将所有节点全部按照相邻节点颜色不同基本要求涂色且中途没有冲突，则证明这个图为二分图，反之不是二分图。

实现代码：

bool isBipartite(vector<vector<int> > &graph) {
        enum Color { // 颜色枚举
            NO_COLOR,
            BLACK = -1,
            WHITE = 1,
        };
        const int n = static_cast<int>(graph.size());
        vector<int> status(n, NO_COLOR);
        bool ans = true;

        auto color = [&](auto self, const int idx) {
            if (!ans) return; // 已确认不为二分图
            int col = status[idx];
            if (col == NO_COLOR) { // 启动涂色
                col = WHITE;
                status[idx] = WHITE;
            }
            for (auto i : graph[idx]) {
                if (!ans) break; // 已确认不为二分图
                if (status[i] == NO_COLOR) { // 深度优先涂色
                    status[i] = -col; // 反色
                    self(self, i); // 递归DFS涂色
                } else if (status[i] != -col) { // 涂色判断，冲突则不为二分图
                    ans = false;
                    break;
                }
            }
        };

        for (int i = 0; ans && i < n; ++i) color(color, i); // 图可能有多个联通分量，因此循环包裹

        return ans;
    }

复杂度分析：

• 时间复杂度：每个节点最多被访问常数次，每条边访问常数次，时间复杂度为O（V+E）（V为点数，E为边数）
• 空间复杂度：涂色状态记录数组O（V），递归深度最高O（V），总计O（V）（V为点数）