本文共 2072 字，大约阅读时间需要 6 分钟。
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: trueExplanation: The graph looks like this:0----1| || |3----2We 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: falseExplanation: The graph looks like this:0----1| \ || \ |3----2We cannot find a way to divide the set of nodes into two independent subsets.
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.j is in graph[i], then i will be in graph[j].Accepted
79,350
Submissions
173,231
--------------------------------------------------------------------------------------------
图着色，DFS或者BFS着色，碰到不行的就是False。实际中，DFS用个栈就可以写非递归，写起来简单很多，如下：
class Solution: def isBipartite(self, graph): colors = {} for i in range(len(graph)): if (i not in colors): colors[i] = 0 sta = [i] while (sta): node = sta.pop() for nxt in graph[node]: if (nxt in colors and colors[nxt] == colors[node]): return False elif (nxt not in colors): #bug2 colors[nxt] = colors[node] ^ 1 #bug1 sta.append(nxt) return Trues = Solution()print(s.isBipartite([[1,3], [0,2], [1,3], [0,2]]))print(s.isBipartite([[1,2,3], [0,2], [0,1,3], [0,2]]))
转载地址：http://dtfoi.baihongyu.com/