Loading problem...
You are given an undirected graph consisting of n nodes, where each node is labeled from 0 to n - 1. The graph is represented as an adjacency list, where graph[u] contains an array of all nodes that are directly connected to node u by an edge.
The graph exhibits the following structural properties:
graph[u] will never contain u).graph[u].v appears in graph[u], then node u will appear in graph[v] (reflecting the undirected nature).Your task is to determine whether the graph can be partitioned into exactly two disjoint sets A and B such that every edge in the graph connects a node from set A to a node from set B. In other words, no edge should connect two nodes within the same set.
A graph satisfying this property is called a bipartite graph or a two-colorable graph. This is equivalent to checking whether you can assign one of two colors to every node such that no two adjacent nodes share the same color.
Return true if the graph can be successfully partitioned into two such sets, and false otherwise.
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]falseConsider the nodes 0, 1, 2, and 3. There exists a triangle formed by nodes 0, 1, and 2 (node 0 connects to both 1 and 2, and nodes 1 and 2 are also connected). In any valid two-set partition, if we place node 0 in set A, both nodes 1 and 2 must be in set B. However, since nodes 1 and 2 are connected by an edge, they cannot both be in the same set. Therefore, no valid partition exists.
graph = [[1,3],[0,2],[1,3],[0,2]]trueWe can partition the nodes into two sets: Set A = {0, 2} and Set B = {1, 3}. Every edge connects a node from set A to a node from set B: edge (0,1) connects A to B, edge (0,3) connects A to B, edge (1,2) connects B to A, and edge (2,3) connects A to B. This forms a valid bipartite structure.
graph = [[1,2],[0,2],[0,1]]falseThis graph forms a triangle with 3 nodes where each node is connected to the other two. A triangle is an odd-length cycle, which cannot be bipartite. No matter how we try to assign nodes to two sets, at least one edge will connect two nodes in the same set.
Constraints