785. Is Graph Bipartite?
785. Is Graph Bipartite?
LWC 72: 785. Is Graph Bipartite?
Problem:
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: 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: 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.
思路： 二分图满足存在子集A和子集B，使得从A出发的边只能连接到B，B出发的边只能连接到A。换句话说，A出发的边不能连到A中的元素。B同理，采用染色法，因为相连的边一定是互异的，如果在不断染色的过程当中，出现冲突的情况，即返回false，全部染色完毕未发现冲突则返回true。
Java版本：
boolean dfs(int[][] G, int[] color, int v, int c) {
color[v] = c;
for (int i = 0; i < color.length; ++i) {
if (G[v][i] != 0) {
if (color[i] != 0 && color[i] == c) return false;
if (color[i] == 0 && !dfs(G, color, i, -c)) return false;
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
int[][] G = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < graph[i].length; ++j) {
G[i][graph[i][j]] = 1;
}
}
for (int i = 0; i < n; ++i) {
if (color[i] == 0) {
if (!dfs(G, color, i, 1)) return false;
}
}
return true;
}Python版本：
class Solution(object):
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
color = [0] * len(graph)
return all(self.dfs(graph, color, v, 1) for v in range(len(graph)) if color[v] == 0)
def dfs(self, graph, color, v, c):
color[v] = c
for to in graph[v]:
if color[to] != 0 and color[to] == c: return False
if color[to] == 0 and not self.dfs(graph, color, to, -c): return False
return True