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:
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.- The graph is undirected: if any element
j
is ingraph[i]
, theni
will be ingraph[j]
.
垂直一条线把graph分为2半,每一半的node只能有链接通向对面一半,不能跟相同一半的node有链接。
把2半分别标记别true跟false
Solution #1 DFS
class Solution { public boolean isBipartite(int[][] graph) { Map<Integer, Boolean> map = new HashMap<>(); for (int i = 0; i < graph.length; i++) { if (!map.containsKey(i) && !dfs(map, graph, i, true)) return false; } return true; } private boolean dfs(Map<Integer, Boolean> map, int[][] graph, int node, boolean flag) { if (map.containsKey(node) && map.get(node) == flag) return false; if (map.containsKey(node)) return true; map.put(node, !flag); for (int neighbor : graph[node]) { if (!dfs(map, graph, neighbor, !flag)) return false; } return true; } }
Solution #2 BFS
class Solution { public boolean isBipartite(int[][] graph) { Mapmap = new HashMap<>(); for (int i = 0; i < graph.length; i++) { if (!map.containsKey(i) && !bfs(map, graph, i)) return false; } return true; } private boolean bfs(Map map, int[][] graph, int node) { Queue que = new LinkedList<>(); que.add(node); map.put(node, true); while (!que.isEmpty()) { int top = que.poll(); for (int neighbor : graph[top]) { if (!map.containsKey(neighbor)) { que.add(neighbor); map.put(neighbor, !map.get(top)); }else if (map.containsKey(neighbor) && map.get(neighbor) == map.get(top)) { return false; } } } return true; } }
No comments:
Post a Comment