Bipartite Graph

Given vertexCount vertices numbered 0 through vertexCount − 1 and a list of undirected edge pairs edges, return true if the vertices can be partitioned into…

Given vertexCount vertices numbered 0 through vertexCount − 1 and a list of undirected edge pairs edges, return true if the vertices can be partitioned into two groups so that every edge joins different groups. Return false otherwise. The graph may be disconnected, contain isolated vertices, repeated edges, or self-loops. A self-loop makes such a partition impossible.

- 1 <= vertexCount <= 10000 - 1 <= edges.length <= 10000 - Each edge contains two integer vertex IDs from 0 to vertexCount - 1 - Edge occurrences retain their order; duplicate edges and self-loops are permitted - Visualizer inputs are limited to 24 vertices and 48 edge occurrences; larger valid graphs remain supported by Run Code and Submit.

Example 1: input vertexCount = 4, edges = [[0,1],[0,3],[1,2],[2,3]]; output true. Groups {0,2} and {1,3} put every edge across the partition.

Example 2: input vertexCount = 4, edges = [[0,1],[0,2],[0,3],[2,1],[3,2]]; output false. The triangle 0–1–2–0 forces two adjacent vertices into the same group.

Category: Graphs. Topic: graph. Difficulty: Medium. Patterns: graph-traversal, bfs, dfs.