为树中的节点添加颜色

Question

我有一棵树，我的任务是找到为节点着色所需的最少颜色数，以便同一父项的两个子项不共享相同的颜色，而且父项和子项不共享相同的颜色。

示例：

number of edges = 5
root = 1

The edges are:

1 2
1 4
2 3
3 5
4 6

输出：

这是我试过的代码：

public static int process(int nodes, int root, int[][] edges) {
    int output = 0;
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < edges.length; i++) {
        int key = edges[i][0];
        List<Integer> v = map.getOrDefault(key, new ArrayList<>());
        map.put(key, v);
        v.add(edges[i][1]);
    }

    Set<Integer> set = new HashSet<>();

    for (int k : map.keySet()) {
        List<Integer> list = map.get(k);
        if (set.add(k)) {
            output++;
        }
        for (int n : list) {
            if (set.add(n)) {
                output++;
            }
        }
    }
    return output;
}

此代码不正确，因为我正在向集合中添加元素并决定需要多少种颜色。解决这个问题的正确方法是什么

Answer 1

最小颜色数等于单个节点最大children数加1。着色很简单：用不同的颜色给根和它的 children 上色。然后用不同于 parent 颜色的颜色给已经着色的 children 的 children 着色，依此类推。

为树中的节点添加颜色

adding colors to nodes in tree

java

algorithm

tree