## 题目描述：

LeetCode 785. Is Graph Bipartite?

Given a `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 ubsets.
```

Note:

• `graph` will have length in range `[1, 100]`.
• `graph[i]` will contain integers in range `[0, graph.length - 1]`.
• `graph[i]` will not contain `i` or duplicate values.

## 解题思路：

Python代码：

``````class Solution(object):
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
edges = collections.defaultdict(set)
for idx, points in enumerate(graph):
colors = {}
def dfs(v, color):
ocolor = 1 - color
for p in edges[v]:
if p not in colors:
colors[p] = ocolor
if not dfs(p, ocolor):
return False
elif colors[p] != ocolor:
return False
return True
for k in edges:
if k in colors: continue
colors[k] = 0
if not dfs(k, 0): return False
return True
``````

## 错误解法：

``````class Solution(object):
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
edges = collections.defaultdict(set)
for idx, points in enumerate(graph):
for points in graph:
for x in range(len(points)):
for y in range(x + 1, len(points)):
if points[y] in edges[points[x]]:
return False
return True
``````

Pingbacks已关闭。

1. Joy 发布于 2018年10月8日 14:48 #

[[4,1],[0,2],[1,3],[2,4],[3,0]] 这个case您的代码通不过诶。。。

2. 在线疯狂 发布于 2018年12月2日 15:03 #

感谢指正，已经更新。