Is Graph Bipartite
Given an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j
for which the edge between nodes i
and j
exists. Each node is an integer between 0
and graph.length - 1
. There are no self edges or parallel edges: graph[i]
does not contain i
, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
思路:bipartite,就是用两种color标记点,相邻的点,不能是一种颜色,题目给的graph刚好是一个adject list
这里注意一点,不能用一个node开始做queue search,因为graph可能有好几个connected component ,所以必须每个点来判断,所以这题用in[] color, 1, -1来表示不同的color,这样就可以判断,所以queue的while循环要写在for(int i = 0; i < graph.length; i++)里面;
class Solution {
public boolean isBipartite(int[][] graph) {
if(graph == null ) {
return false;
}
// 0 uncolor;
// 1 one color
// -1 the other color;
int[] color = new int[graph.length];
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < graph.length; i++) {
if(graph[i] != null && color[i] == 0) {
queue.offer(i);
color[i] = 1;
}
while(!queue.isEmpty()) {
int size = queue.size();
for(int j = 0; j < size; j++) {
Integer node = queue.poll();
for(Integer neighbor: graph[node]) {
if(color[neighbor] == color[node]) {
return false;
}
if(color[neighbor] == 0) {
color[neighbor] = -color[node];
queue.offer(neighbor);
}
}
}
}
}
return true;
}
}
上一篇: js获取文本框值
下一篇: python入门 Day07
推荐阅读
-
graph.exe是什么进程 作用是什么 graph进程查询
-
Graph Search、大数据和视频网站的春天
-
Python3 - plotly, graph_objs, 炫酷的数据可视化
-
性能分析工具 —— flame graph 火焰图
-
李开复解读Graph Search:两个伟大公司进入彼此领域,鹿死谁手还
-
Slickflow.Graph 开源工作流引擎快速入门之四: 图形编码建模工具使用手册
-
c/c++ 有向无环图 directed acycline graph
-
LeetCode 785. Is Graph Bipartite?
-
【leetcode】785. Is Graph Bipartite?
-
Chart and Graph 柱状图