785. Is Graph Bipartite?

Probelm:
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.
 Analysis:
这种太数学的题最恶心,没刷过100%做不出来,遇到只有认栽。主要就是标记颜色,一开始让所有node颜色都为0,然后用BFS或者DFS遍历。把edge两端的node标记为不同颜色1, -1。如果遇到edge两边的node颜色一样则说明不是bipartite.
Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int[] color = new int[graph.length];
       
        
        for (int i = 0; i < graph.length; i++) {
            if (color[i] != 0)
                continue;
            queue.offer(i);
            color[i] = 1;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int neib: graph[cur]) {
                    if (color[neib] == 0) {
                        color[neib] = -1 * color[cur];
                        queue.offer(neib);
                    } else {
                        if (color[neib] == color[cur])
                            return false;    
                    }
                }
            }
        }
        
        return true;
    }
}

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array