题目描述:
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 containi
or duplicate values.
题目大意:
以邻接表形式给定无向图graph,判断是否为二分图
解题思路:
染色 + DFS
遍历顶点,若顶点未被染色,则染色为红色(0),并将其相邻节点染成黑色(1),递归执行;若遇到冲突,则返回False
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):
for p in points: edges[idx].add(p)
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
错误解法:
将邻接表转化为邻接矩阵
然后判断每一组顶点集互相之间是否有边相连,若存在则返回False
返回True
Python代码(Wrong Answer):
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 p in points: edges[idx].add(p)
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
本文链接:http://bookshadow.com/weblog/2018/02/18/leetcode-is-graph-bipartite/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
Joy 发布于 2018年10月8日 14:48 #
[[4,1],[0,2],[1,3],[2,4],[3,0]] 这个case您的代码通不过诶。。。
在线疯狂 发布于 2018年12月2日 15:03 #
感谢指正,已经更新。