判断二分图

/*
 * Problem: Determine if a given undirected graph is bipartite.
 * Approach: Use Stream API for the initialization and processing of nodes.
 * We use BFS with a queue to assign colors and check conditions.
 */
import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = IntStream.generate(() -> 0).limit(n).toArray();
        for (int i = 0; i < n; i++) {
            if (colors[i] == 0) { // Node is uncolored
                if (!bfsCheck(graph, i, colors)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean bfsCheck(int[][] graph, int start, int[] colors) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        colors[start] = 1; // Start coloring with color A
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph[node]) {
                if (colors[neighbor] == 0) { // If the neighbor is uncolored
                    colors[neighbor] = -colors[node]; // Assign opposite color
                    queue.offer(neighbor);
                } else if (colors[neighbor] == colors[node]) { // If the neighbor has the same color
                    return false; // Not a bipartite graph
                }
            }
        }
        return true;
    }
}