为树中的节点添加颜色

Question

我有一个树，我的任务是找到为节点上色所需的最小颜色计数，以便同一父节点的两个子节点不共享相同的颜色，也父节点和子节点不共享相同的颜色。

例子:

number of edges = 5
root = 1
The edges are:
1 2
1 4
2 3
3 5
4 6

输出:

3

这是我尝试的代码:

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

最小颜色数等于单个节点的最大子节点数加1。上色很简单:用不同的颜色给根和它的子根上色。然后给已经上色的子元素的子元素上色，颜色与其父元素的颜色不同，以此类推。