Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Assign colors to vertices 1, 2, …, n in order.
  2. 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");
    }
}

Solve M-Coloring Problem online · All practice problems