Check If Undirected Graph Is Bipartite
Given an undirected graph with n nodes numbered from 0 to n - 1, determine whether the graph is bipartite.
The graph is represented by a list of strings. The string at index u contains the comma-separated nodes adjacent to node u. An empty string means that the node has no neighbors.
A graph is bipartite when its nodes can be divided into two independent sets such that every edge connects a node from one set to a node in the other set.
The graph can be disconnected. Return true if every connected component is bipartite; otherwise, return false.
Method Signature
boolean isBipartite(List<String> graph)
Parameters
graph represents the adjacency list of the graph.graph.get(u) contains the comma-separated neighbors of node u.- Each neighbor value is an integer between
0 and graph.size() - 1.
Returns
- Returns
true if the graph is bipartite.
- Returns
false if the graph is not bipartite.
Graph Properties
- The graph contains no self-edges.
- No adjacency string contains duplicate node values.
- If node
v appears in the neighbors of node u, then node u appears in the neighbors of node v.
- The graph may contain multiple disconnected components.
Constraints
1 <= graph.size() <= 100- Each node has between
0 and graph.size() - 1 neighbors.
- Every neighbor is between
0 and graph.size() - 1.
- A node is never listed as its own neighbor.
- All neighbors of a node are unique.
Examples
Example 1
isBipartite(graph = List.of("1,2", "0,2", "0,1"))
Output: false
The three nodes form an odd cycle, so they cannot be divided into two valid independent sets.
Example 2
isBipartite(graph = List.of("1", "0", "3", "2,4", "3"))
Output: true
Both disconnected components can be divided into two independent sets.
Example 3
isBipartite(graph = List.of("", "2,4", "1,3", "2,4", "1,3"))
Output: true
Node 0 is isolated, and the remaining nodes form an even cycle, so the complete graph is bipartite.