原题链接：Leecode 785. 判断二分图

BFS

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int> color(n,0);
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            if(!color[i])
            {
                color[i]=1;
                q.push(i);
            }
            while(!q.empty())
            {
                int cur=q.front();
                q.pop();
                for(auto x: graph[cur])
                {
                    if(color[x]==color[cur]) return false;
                    else if(color[x]==0)
                    {
                        q.push(x);
                        color[x]=-color[cur];
                    }
                }
            }
        }
        return true;
    }
};

DFS

class Solution {
public:
    vector<int> color;
    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        color.resize(n);
        for(int i=0;i<n;i++)
        {
            if(!color[i] && !dfs(graph,i,1)) return false;
        }
        return true;
    }
    bool dfs(vector<vector<int>>& graph,int i,int col)
    {
        color[i]=col;
        for(auto x: graph[i])
        {
            if(color[x]==color[i]) return false;
            else if(!color[x] && !dfs(graph,x,-col)) return false;
        }
        return true;
    }
};