leetcode 785. Is Graph Bipartite?

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.
leetcodeはDFS検索のテーマであることを示しています.では、テーマを解読します.無方向図を1枚ください.n個のノードがあります.もしこの無方向図を2つのサブ図に分けることができれば、元の無方向図graphの無辺の2つの端点をこの2つのサブ図に分けることができます.そうでなければ、return false.依然として染色法を用い、

-1色がない

1は色

を表す.

0は別の色を表すため、隣接する端点の色が異なることを保証するだけでよいので、DFSのある定点では、隣接するノードに対して1 - colorを使用してDFSを最初の頂点から継続し、すでに色があれば戻る.

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        Arrays.fill(colors, -1);            

        for (int i = 0; i < n; i++) {             
            if (colors[i] == -1 && !validColor(graph, colors, 0, i)) {
                return false;
            }
        }
        return true;
    }

    public boolean validColor(int[][] graph, int[] colors, int color, int node) {
        if (colors[node] != -1) {
            return colors[node] == color;
        }       
        colors[node] = color;       
        for (int next : graph[node]) {
            if (!validColor(graph, colors, 1 - color, next)) {
                return false;
            }
        }
        return true;
    }
}