Can a Graph Be Colored With at Most M Colors?
Implement canColorGraph
You're given an undirected graph with
vertexCount vertices and a list of edges, plus a number of available colors m. Determine whether every vertex can be given one of the m colors so that no edge ever connects two same-colored vertices.
Assigning colors to every vertex first and validating the entire graph afterward finds the right answer, but a single bad choice made early on stays hidden until the whole coloring is complete and the full edge list gets scanned. Building each vertex's own list of neighbors up front turns that after-the-fact scan into a direct, immediate check — a color that conflicts with a vertex's own neighbors is ruled out before it's ever assigned, not discovered afterward by re-examining the whole graph.
Example 1:
Input: vertexCount = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]], m = 2
Output: false
Example 2:
Input: vertexCount = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]], m = 3
Output: true
Example 3:
Input: vertexCount = 3, edges = [], m = 1
Output: true
+ 5 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ vertexCount ≤ 12 - ●
0 ≤ edges.length ≤ vertexCount · (vertexCount − 1) / 2, each edge a pair of distinct vertex indices - ●
1 ≤ m ≤ vertexCount - ●
Two vertices joined by an edge may never share a color
vertexCount =
5
edges =
[[0,1], [1,2], [2,3], [3,4], [4,0]]
m =
2