//
// Created by 高森森 on 2022/1/25.
//

#ifndef LEETCODE_SOLUTION7_H
#define LEETCODE_SOLUTION7_H
#include<iostream>
using namespace std;
#include<vector>
#include<queue>

class Solution7 {
public:
    static constexpr int NCOLOR=0;
    static const int RED=1;
    static const int GREEN=2;
    vector<int>color;
    bool isValid;
    void dfs(int node,int c, vector<vector<int>>&graph)
    {
        color[node]=c;
        int cNext=(c==RED?GREEN:RED);
        for(int neigh:graph[node])
        {
            if(color[neigh]==NCOLOR)
            {
                dfs(neigh,cNext,graph);
                if(!isValid)
                {
                    return;
                }
            }
            else if(cNext!=color[neigh]){
                isValid= false;
                return;
            }
        }
    }
    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        isValid= true;
        color.assign(n,NCOLOR);
        for(int i=0;i<n;i++)
        {
            if(color[i]==NCOLOR)
            {
                dfs(i,RED,graph);
                if(!isValid)
                {
                    return isValid;
                }
            }
        }
        return isValid;
    }
    bool isBipartite1(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int>color(n,NCOLOR);
        for(int i=0;i<n;i++)
        {
            if(color[i]==NCOLOR)
            {
                queue<int>queue;
                queue.push(i);
                color[i]=RED;
                while(!queue.empty())
                {
                    int node=queue.front();
                    int cNext=(color[node]==RED?GREEN:RED);
                    queue.pop();
                    for(int nei:graph[node])
                    {
                        if(color[nei]==NCOLOR)
                        {
                            queue.push(nei);
                            color[nei]=cNext;
                        }
                        else if(color[nei]!=cNext)
                        {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};


#endif //LEETCODE_SOLUTION7_H