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

╰半夏微凉° 2021-09-28 12:32 209阅读 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 条评论，209人围观）

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

相关阅读

相关 785. 判断二分图

存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph\[u\] 是一个节点数组

浅浅的花香味﹌/ 2024年03月27日 08:44/ 0 赞/ 76 阅读

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

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

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

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

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

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

相关 785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合

╰+攻爆jí腚メ/ 2023年02月26日 14:27/ 0 赞/ 17 阅读

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

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

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

相关 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 赞/ 199 阅读

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

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

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

相关判断二分图染色法 NYOJ 1015

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

深藏阁楼爱情的钟/ 2022年06月03日 01:36/ 0 赞/ 193 阅读

相关纸上谈兵: 图 (graph)

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！图(graph)是一种比较松散的数据结构。它有一

快来打我*/ 2021年11月26日 11:42/ 0 赞/ 345 阅读

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

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

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