本溪市住房和城乡建设局网站,网站的网络推广,曲阜网架公司,不知此网站枉做男人的网站文章目录1. 题目2. 解题1. 题目
给定一个无向图graph#xff0c;当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B#xff0c;并使图中的每一条边的两个节点一个来自A集合#xff0c;一个来自B集合#xff0c;我们就将这个图称为二分…
文章目录1. 题目2. 解题1. 题目
给定一个无向图graph当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B并使图中的每一条边的两个节点一个来自A集合一个来自B集合我们就将这个图称为二分图。
graph将会以邻接表方式给出graph[i]表示图中与节点i相连的所有节点。 每个节点都是一个在0到 graph.length-1 之间的整数。 这图中没有自环和平行边 graph[i] 中不存在i并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。注意:
graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。来源力扣LeetCode 链接https://leetcode-cn.com/problems/is-graph-bipartite 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
对所有没有染色的节点进行染色从任意一点出发其染成颜色1与其直接连接的染成颜色2若遇到相同的则不可分
class Solution {
public:bool isBipartite(vectorvectorint graph) {int n graph.size();vectorint color(n, 0);for(int i 0; i n; i){if(color[i] ! 0)//染过了跳过continue;queueint q;q.push(i);color[i] 1;//染成颜色1开始bfsint curColor 1, newColor, id, k;while(!q.empty()){id q.front();q.pop();curColor color[id];newColor curColor1 ? 2 : 1;for(k 0; k graph[id].size(); k){if(color[graph[id][k]] 0){q.push(graph[id][k]);color[graph[id][k]] newColor;}else if(color[graph[id][k]] curColor)return false;}}}return true;}
};52 ms 11.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
