leetcode-cn Daily Challenge on July 16th, 2020.
Difficulty : Medium
Related Topics : BFS、DFS、Graph
Given an undirected
graph
, returntrue
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 indexesj
for which the edge between nodesi
andj
exists. Each node is an integer between0
andgraph.length - 1
. There are no self edges or parallel edges:graph[i]
does not containi
, and it doesn't contain any element twice.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}.
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.
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]
.
- mine
- Java
- DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.9 MB, less than 78.94% of Java online submissions
// O(N)time // O(N)space int[] colors; boolean res; public boolean isBipartite(int[][] graph) { res = true; int n = graph.length; colors = new int[n]; for(int i = 0; i < n; i++){ if(colors[i] != 0){ continue; } dfs(i, 1, graph); } return res; } void dfs(int index, int color, int[][] graph){ colors[index] = color; color = color == 1 ? 2 : 1; for(int i : graph[index]){ if(colors[i] == 0){ if(!res){ return; } dfs(i, color, graph); }else if(colors[i] != color){ res = false; return; } } }
- DFS
- Java
- the most votes
-
DFS
Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.9 MB, less than 74.75% of Java online submissions
// O(N)time // O(N)space public boolean isBipartite(int[][] graph) { int n = graph.length; int[] colors = new int[n]; for (int i = 0; i < n; i++) { //This graph might be a disconnected graph. So check each unvisited node. if (colors[i] == 0 && !validColor(graph, colors, 1, i)) { return false; } } return true; } public boolean validColor(int[][] graph, int[] colors, int color, int node) { if (colors[node] != 0) { return colors[node] == color; } colors[node] = color; for (int next : graph[node]) { if (!validColor(graph, colors, -color, next)) { return false; } } return true; }
-
BFS
Runtime: 3 ms, faster than 30.19%, Memory Usage: 51.9 MB, less than 5.04% of Java online submissions
// O(N)time // O(N)space public boolean isBipartite(int[][] graph) { int len = graph.length; int[] colors = new int[len]; for (int i = 0; i < len; i++) { if (colors[i] != 0) continue; Queue<Integer> queue = new LinkedList<>(); queue.offer(i); colors[i] = 1; // Blue: 1; Red: -1. while (!queue.isEmpty()) { int cur = queue.poll(); for (int next : graph[cur]) { if (colors[next] == 0) { // If this node hasn't been colored; colors[next] = -colors[cur]; // Color it with a different color; queue.offer(next); } else if (colors[next] != -colors[cur]) { // If it is colored and its color is different, return false; return false; } } } } return true; }
-