Practice › Recursion & Backtracking
M-Coloring Problem
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Samsung
Can the vertices of the undirected graph be colored with at most k colors so that no edge joins two vertices of the same color? Print YES or NO.
Input
First line: n m k. Next m lines: u v — an edge (vertices are 1..n).
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 12
- 0 ≤ m ≤ n(n−1)/2
- 1 ≤ k ≤ n
Color vertex 1, 2, 3, … in order, trying every color that no already-colored neighbour uses; backtrack when a vertex has no valid color.
Example 1
Input
4 5 3 1 2 2 3 3 4 4 1 1 3
Output
YES
Example 2
Input
3 3 2 1 2 2 3 3 1
Output
NO
Hints
- Assign colors to vertices 1, 2, …, n in order.
- For vertex v, try colors 1..k that no already-colored neighbour has. If none works, go back and change the previous vertex.
Approach
Backtracking over vertices: go(v) succeeds if v > n. For each color c, check v's neighbours; if none has color c, assign it and call go(v + 1); on failure reset and try the next color. If every color fails, return false so the caller tries something else. With n ≤ 12 and pruning, this is fast.
Complexity: O(k^n · n) worst case · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<vector<int>> adj;
vector<int> col;
bool go(int v) {
if (v > n) return true;
for (int c = 1; c <= k; c++) {
bool ok = true;
for (int u : adj[v])
if (col[u] == c) ok = false;
if (!ok) continue;
col[v] = c;
if (go(v + 1)) return true;
col[v] = 0;
}
return false;
}
int main() {
cin >> n >> m >> k;
adj.assign(n + 1, {});
col.assign(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cout << (go(1) ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m, k = data[0], data[1], data[2]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[3 + 2 * i], data[4 + 2 * i]
adj[u].append(v)
adj[v].append(u)
col = [0] * (n + 1)
def go(v):
if v > n:
return True
for c in range(1, k + 1):
if any(col[u] == c for u in adj[v]):
continue
col[v] = c
if go(v + 1):
return True
col[v] = 0
return False
print("YES" if go(1) else "NO")Java solution
import java.util.*;
public class Main {
static int n, k;
static List<List<Integer>> adj = new ArrayList<>();
static int[] col;
static boolean go(int v) {
if (v > n) return true;
for (int c = 1; c <= k; c++) {
boolean ok = true;
for (int u : adj.get(v))
if (col[u] == c) ok = false;
if (!ok) continue;
col[v] = c;
if (go(v + 1)) return true;
col[v] = 0;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int m = sc.nextInt();
k = sc.nextInt();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
col = new int[n + 1];
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
System.out.println(go(1) ? "YES" : "NO");
}
}