Is Graph Bipartite?

1class Solution {
2    public boolean isBipartite(int[][] graph) {
3        int n = graph.length;
4        int[] colors = new int[n];
5        // Initialize all vertices as uncolored
6        Arrays.fill(colors, -1);
7
8        for (int i = 0; i < n; i++) {
9            // If the current node is not colored, apply DFS coloring
10            if (colors[i] == -1) {
11                if (!dfs(graph, colors, i, 0)) {
12                    return false;
13                }
14            }
15        }
16        return true;
17    }
18
19    private boolean dfs(int[][] graph, int[] colors, int node, int color) {
20        // Assign color to the current node
21        colors[node] = color;
22
23        // Traverse all connected nodes
24        for (int neighbor : graph[node]) {
25            // If the neighbor is not colored, assign the opposite color and continue DFS
26            if (colors[neighbor] == -1) {
27                if (!dfs(graph, colors, neighbor, 1 - color)) {
28                    return false;
29                }
30            }
31            // If the neighbor has the same color, the graph is not bipartite
32            else if (colors[neighbor] == color) {
33                return false;
34            }
35        }
36        return true;
37    }
38}