785. 判断二分图

╰+攻爆jí腚メ 2023-02-26 14:27 16阅读 0赞

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph\[i\]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph\[i\] 中不存在i，并且graph\[i\]中没有重复的值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]

来源：力扣（LeetCode）[添加链接描述][Link 1]  
我的代码：  
广度优先遍历，从一个结点开始染色,分别用0，1标记

class Solution {
        
    public:
        bool isBipartite(vector<vector<int>>& graph) {
        
            if(graph.size() == 0) return false;
            int len = graph.size();
            int flag[len];
            for(int i = 0; i < len; i++) flag[i] = -1;//初始化为-1
            
            queue<int> q;
            for(int i = 0; i < len; i++){
        
                if(flag[i] == -1) //如果结点未标记，开始标记
            {
        q.push(i);
            flag[i] = 1;
            while(!q.empty()){
        
                int temp = q.front();
                int size = graph[temp].size();
                for(int i = 0; i < size; i++){
        
                    if(flag[graph[temp][i]] == -1) {
        //邻居未标记
                        q.push(graph[temp][i]);
                        flag[graph[temp][i]] = (flag[temp]+1) % 2;
                    }else if(flag[graph[temp][i]] == flag[temp]) {
        //邻居标记相同
                        return false;
                    }else continue;//邻居已标记
                }
                q.pop();
            }}
            
            }
            return true;//全部成功染色
        }
    };

官方标准dfs：

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);
                }
                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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70]: /images/20230209/03802afa0dff48279ce1ab9f5b198fb7.png
[Link 1]: https://leetcode-cn.com/problems/is-graph-bipartite