785 Is Graph Bipartite?

class Solution {
    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length == 0) return false;

        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++){
            if (color[i] == -1){
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                color[i] = 0;

                while (!q.isEmpty()){
                    int cur = q.poll();

                    for (int nei : graph[cur]){
                        if (color[nei] == -1){
                            q.offer(nei);
                            color[nei] = color[cur] ^ 1;
                        }
                        else{
                            if (color[nei] == color[cur]) return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}

results matching ""

    No results matching ""