Can the Graph Be Coloured?
Advanced
A graph has n nodes numbered 0 to n - 1 and some edges, each [u, v] joining two nodes. Return True if every node can be given one of colors colours so that the two ends of every edge have different colours. An edge from a node to itself (u == v) can never be coloured, so the answer is then False.
Examples
Example 1
Input:
can_color_graph(3, [[0, 1], [1, 2], [0, 2]], 3)
Output:
True
Example 2
Input:
can_color_graph(3, [[0, 1], [1, 2], [0, 2]], 2)
Output:
False
Constraints
0 <= n <= 140 <= len(edges) <= 400 <= u, v < n1 <= colors <= 5
Theory
Go to TheoryKeywords
dsa-sheetrecursionbacktracking-puzzles
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.