[leetcode]图算法之二分图染色法/BFS的运用785. Is Graph Bipartite?

╰半夏微凉° 2021-09-28 12:32 247阅读 0赞

### 图算法之二分图染色法/BFS的运用 ###

*  题目
 *  解析
 *  答案

# 题目 #

[leetcode入口][leetcode]

# 解析 #

二分图，其实就是把点分成两个集合  
使用BFS，相邻曾的节点属于不同的集合，如果在BFS的过程中遇到了之前访问过的节点，就说明不能分成两个集合

# 答案 #

//BFS
    class Solution { 
    public:
        bool isBipartite(vector<vector<int>>& graph) { 
            vector<int> colors(graph.size(),0);
            
            queue<int> q;
            while(!q.empty()){ 
                q.pop();
            }
            
            for(int i=0;i<graph.size();i++){ 
                if(colors[i]) continue;
                
                colors[i]=1;
                
                q.push(i);
                
                while(!q.empty()){ 
                    int t=q.front(); q.pop();
                    
                    for(int i=0;i<graph[t].size();i++){ 
                        int j=graph[t][i];
                        
                        if(colors[j]==colors[t]) return false;
                        if(colors[j]) continue;
                        
                        colors[j]=colors[t]*(-1);
                        
                        q.push(j);
                    }
                }
            }
            return true;
        }
    };

[leetcode]: https://leetcode.com/problems/is-graph-bipartite/

发表评论取消回复

表情：

评论列表（有 0 条评论，247人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_二分图_中等_785. 判断二分图

目录 1.题目 2.思路 3.代码实现（Java） 1.题目存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1

左手的ㄟ右手/ 2023年10月06日 22:37/ 0 赞/ 123 阅读

相关染色法判定二分图 AcWing 860. 染色法判定二分图

染色法判定二分图 AcWing 860. 染色法判定二分图原题链接 [AcWing 860. 染色法判定二分图][AcWing 860.] 算法标签二分

超、凢脫俗/ 2023年09月28日 12:49/ 0 赞/ 100 阅读

相关算法-图染色法 DFS/BFS-判断二分图

算法-图染色法 DFS/BFS-判断二分图 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/is-graph

刺骨的言语ヽ痛彻心扉/ 2023年02月27日 05:39/ 0 赞/ 65 阅读

相关 [Leetcode][第785题][JAVA][判断二分图][BFS][DFS]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

àì夳堔傛蜴生んèń/ 2023年02月26日 15:26/ 0 赞/ 66 阅读

相关图的BFS算法

BFS：Breadth-First-Search 介绍 BFS:广度优先搜索类似于树的按层次遍历过程思想 1. 访问起始点v 2. 之后，依

末蓝、/ 2023年02月20日 13:39/ 0 赞/ 18 阅读

相关 Leetcode 785. 判断二分图

Leetcode 785. 判断二分图 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.

向右看齐/ 2023年02月09日 10:27/ 0 赞/ 64 阅读

相关 Leetcode——BFS在树和图结构中的运用

pythons模板 BFS 使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS 总共有两个模板：如果不需要确定当前遍历到了哪

港控/mmm°/ 2022年10月29日 13:29/ 0 赞/ 191 阅读

相关 leetcode 133. Clone Graph 图遍历BFS + 避免循环

Clone an undirected graph. Each node in the graph contains a label and a list of its nei

喜欢ヅ旅行/ 2022年06月08日 05:57/ 0 赞/ 261 阅读

相关二部图(染色法判断二部图)

二部图时间限制：1000 ms | 内存限制：65535 KB 难度：1 描述二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也

偏执的太偏执、/ 2022年06月08日 01:23/ 0 赞/ 283 阅读

相关 [leetcode]图算法之二分图染色法/BFS的运用785. Is Graph Bipartite?

图算法之二分图染色法/BFS的运用题目解析答案题目 [leetcode入口][leetcode] 解析二分图，其实就是把点分成

╰半夏微凉°/ 2021年09月28日 12:32/ 0 赞/ 248 阅读