// 判断二分图
// 二分图指可以将图的顶点集分为两个独立的子集 A 和 B，图中每条边的的两个结点都分别属于 A 或 B
// 一个简单的思路是涂色：将每条边的两个顶点涂为不同的颜色，
// 如果出现一条边的两个顶点是同一颜色，则该图一定不是二分图

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> colors = vector<int>(n);
        for(int i = 0; i < n; i++) {
            // 如果没有被涂色，并且尝试涂色失败
            if(colors[i] == 0 && !dfs(graph, colors, 1, i)) {
                return false;
            }
        }
        return true;
    }

private:
    bool dfs(vector<vector<int>>& graph, vector<int>& colors, int color, int i) {
        // 如果已被涂色
        if(colors[i])
            return colors[i] == color;

        // 如果尚未被涂色
        // 涂色，并 dfs 判断是否有冲突
        colors[i] = color;
        for(int j = 0; j < graph[i].size(); j++) {
            if(!dfs(graph, colors, -color, graph[i][j]))
                return false;
        }
        return true;
    }
};