LeetCode 785. Is Graph Bipartite?
原题链接在这里：https://leetcode.com/problems/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.
Note:
graphwill have length in range[1, 100].graph[i]will contain integers in range[0, graph.length - 1].graph[i]will not containior duplicate values.- The graph is undirected: if any element
jis ingraph[i], theniwill be ingraph[j].
题解：
Try to color the nodes with 2 different colors. Two adjcent nodes can't have same colors.
Use BFS to traverse nodes. At the beginning, put node 0 in the queue, color it as 1.
While queue is not empty, poll the cur node. For neighbors, if nei is not traversed before, color nei with -colors[cur].
If nei is traversed and its color is the same as cur, then 2 adjcent nodes have same color, return false.
For questions like this, traversed nodes need to be put into multiple categories, use array of integers to mark their categories.
Note: graph may not be one component. Thus for each node that is still 0, still need BFS on it.
Time Complexity: O(V+E). V = graph.length. E is count of all the edges.
Space: O(V).
AC Java:
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int [] colors = new int[n];
for(int i = 0; i<n; i++){
if(colors[i] == 0){
LinkedList<Integer> que = new LinkedList<>();
colors[i] = 1;
que.add(i);
while(!que.isEmpty()){
int cur = que.poll();
for(int nei : graph[cur]){
if(colors[nei] == 0){
colors[nei] = -colors[cur];
que.add(nei);
}else if(colors[nei] == colors[cur]){
return false;
}
}
}
}
}
return true;
}
}
Use DFS to iterate nodes.
Start with first node with color 0, dfs try to color it with desiredColor.
For its neighbors, if they are not colored before, try to color them with -desiredColor.
Otherwise, check if they have the color they should have.
If any of them not, then return false.
Time Complexity: O(V+E).
Space: O(V). stack space.
AC Java:
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int [] colors = new int[n];
for(int i = 0; i<n; i++){
if(colors[i] == 0 && !dfs(i, 1, colors, graph)){
return false;
}
}
return true;
}
private boolean dfs(int cur, int desiredColor, int [] colors, int[][] graph){
if(colors[cur] == 0){
colors[cur] = desiredColor;
for(int nei : graph[cur]){
if(!dfs(nei, -desiredColor, colors, graph)){
return false;
}
}
return true;
}else if(colors[cur] != desiredColor){
return false;
}else{
return true;
}
}
}
最新文章
- Tire树入门专题
- 深入理解javascript作用域系列第三篇——声明提升(hoisting)
- poj2154-color-polyan次二面体+欧拉函数优化
- 日程管理控件 glDatePicker
- 反编译c#的相关问题
- 【openstack报错】【metadata问题】‘http://169.254.169.254/2009-04-04/meta-data/instance-id’ failed : url error [[Errno 111] Connection refused]
- ipython与python的区别
- ArcMap制图_显示指定区域地图内容
- 百度2015校园招聘自然语言处理project师面试
- C# 利用SMTP异步发送邮件
- UVa 10720 - Graph Construction
- Robotframe work学习之初（二）
- Swift3 GCD队列优先级说明
- 201621123050 《Java程序设计》第8周学习总结
- Python浅谈requests三方库
- Go语言的通道(2)-缓冲通道
- 无线智联-程序篇：让python与matlab牵手
- Python 爬虫 解析库的使用 --- Beautiful Soup
- mysql 查询缓存优化文章
- HDUOJ----旋转的二进制