785. 判断二分图-7月16日

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        set<int> A,B;
        return check(0,graph,A,B,0);
    }
    bool check(int i,vector<vector<int>>& graph,set<int> A,set<int> B,int type){
        if(i==graph.size()) return true;//0.如果i等于graph.length,那么返回true
        if(type == 0){//1.把i加入A,把graph[i]中所有元素加入B
            A.insert(i);
            for(auto iter : graph[i])   B.insert(iter);
        }else{
            B.insert(i);
            for(auto iter : graph[i])   A.insert(iter);
        }
        for(auto iter: A){//2.判断A和B中是否有重复元素，若有返回false
            if(B.count(iter)>0) return false;
        }
        bool R1 = check(i+1,graph,A,B,0);
        if(R1==true)return true;
        bool R2 = check(i+1,graph,A,B,1);
        return R1 || R2;

    }

};
/**
重新整理一下思路：
递归的出口条件：遍历完最后一个节点i=graph.length or 两个集合中存在重复元素
check(int i,vector<vector<int>>& graph,vector<int> A,vector<int> B,int type)递归函数内部的执行过程：
0.如果i等于graph.length,那么返回true
1.把i加入A,把graph[i]中所有元素加入B
2.判断A和B中是否有重复元素，若有返回false
3.bool R1 = check(graph,A,B,0)
4.bool R2 = check(graph,A,B,1)
5.return R1 || R2
*/

/**
实质上就是找一种分类A和B:
i属于A时，若j属于B，graph[i]中一定没有j;反之亦然
1.强行暴力枚举所有分类的话,时间复杂度会达到2^n以上
2.遍历graph，对每个graph[i],可以产生两种结果： 
    graph[i]中的元素属于A，i属于B    or     graph[i]中的元素属于B，i属于A
    接着检查是否与现有集合有冲突，若没有则继续，若有则返回
*/

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int constexpr NOCOLOR=0;
        int constexpr RED=1;
        int constexpr GREEN=2;
        int numofNodes=graph.size();
        vector<int> nodestocheck;
        vector<int> colors(numofNodes,NOCOLOR);
        //colors[0]=RED;
        //nodestocheck.push_back(0);
        for(int i=0;i<numofNodes;i++){
            if(colors[i]!=NOCOLOR)continue;
            colors[i]=RED;
            printf("%dinn",i);
            nodestocheck.push_back(i);
            while(!nodestocheck.empty()){
                int presentNode = *nodestocheck.begin();
                nodestocheck.erase(nodestocheck.begin());
                printf("%doutn",presentNode);
                for(auto iter:graph[presentNode]){
                    if(colors[iter]==colors[presentNode]){
                        //printf("%d:%d:%d",colors[iter],iter,presentNode);
                        return false;
                    }else
                    if(colors[iter]==NOCOLOR){
                        colors[iter]= colors[presentNode]==RED?GREEN:RED;
                        nodestocheck.push_back(iter);
                        printf("%dinn",iter);
                    }
                }
            }
        }
        return true;
    }

};

class Solution {
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;
    vector<int> color;
    bool valid;

public:
    void dfs(int node, int c, const vector<vector<int>>& graph) {
        color[node] = c;
        int cNei = (c == RED ? GREEN : RED);
        for (int neighbor: graph[node]) {
            if (color[neighbor] == UNCOLORED) {
                dfs(neighbor, cNei, graph);
                if (!valid) {
                    return;
                }
            }
            else if (color[neighbor] != cNei) {
                valid = false;
                return;
            }
        }
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        valid = true;
        color.assign(n, UNCOLORED);
        for (int i = 0; i < n && valid; ++i) {
            if (color[i] == UNCOLORED) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }
};

class Solution {
private:
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int GREEN = 2;
    vector<int> color;

public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, UNCOLORED);
        for (int i = 0; i < n; ++i) {
            if (color[i] == UNCOLORED) {
                queue<int> q;
                q.push(i);
                color[i] = RED;
                while (!q.empty()) {
                    int node = q.front();
                    int cNei = (color[node] == RED ? GREEN : RED);
                    q.pop();
                    for (int neighbor: graph[node]) {
                        if (color[neighbor] == UNCOLORED) {
                            q.push(neighbor);
                            color[neighbor] = cNei;
                        }
                        else if (color[neighbor] != cNei) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};