Is Graph Bipartite?

Check if a Graph is Bipartite Problem Statement A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets, U and V, such that every edge connects a vertex in U to one in V. In other words, it is possible to color a graph with two colors such that no two adjacent nodes have the same color. Given an undirected graph represented by its adjacency list adj with V vertices (0 based index), determine if the graph is bipartite. Input Specification The input describes an undirected graph. The first line implicitly defines V, the number of vertices, based on the size of the adjacency list. Vertices are 0 indexed. The graph structure is provided as an adjacency list where adj[i] contains a list of vertices adjacent to vertex i. Output Specification Return 1 if the graph is bipartite, 0 otherwise. Sample Test Cases Example 1: Input: Output: Explanation: This is a linear graph (0 1 2) which is bipartite. We can color vertex 0 with color A, vertex 1 with color B, and vertex 2 with color A. No adjacent vertices have the same color. Example 2: Input: Output: Explanation: This graph contains an odd length cycle (e.g., 0 2 3 0). If we attempt to color it: Color vertex 0 with color A. Vertices 2 and 3, being adjacent to 0, must be colored B. However, vertex 2 and vertex 3 are also adjacent to each other. Since both are colored B, this violates the bipartite property. Thus, the graph is not bipartite.