一 问题描述

二 算法说明

本问题为图的 m 着色问题，可采用回溯法（m 叉树）解决。

三 代码

package com.platform.modules.alg.alglib.p2819;

public class P2819 {
    public String output = "";
    private int n, m;
    private int a = 1, b = 1;
    int sum = 0;
    int graph[][] = new int[20][20];
    int color[] = new int[20];

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        m = Integer.parseInt(word[2]);
        for (int i = 1; i < line.length; i++) {
            String[] connection = line[i].split(" ");
            graph[Integer.parseInt(connection[0])][Integer.parseInt(connection[1])] = 1;
            graph[Integer.parseInt(connection[1])][Integer.parseInt(connection[0])] = 1;
        }
        backtrack(1);
        output += sum;
        return output;
    }

    boolean ok(int c) {
        for (int k = 1; k <= n; k++) {
            if (graph[c][k] == 1 && color[c] == color[k]) {
                return false;
            }
        }
        return true;
    }

    void backtrack(int cur) {
        if (cur > n) {
            sum++;
        } else {
            for (int i = 1; i <= m; i++) {
                color[cur] = i;
                if (ok(cur)) {
                    backtrack(cur + 1);
                }
                color[cur] = 0;
            }
        }
    }
}

四 测试