我有一棵樹，我的任務是找到為節點著色所需的最小顏色數，以便同一父級的兩個子級不會共享相同的顏色，父級和子級也不會共享相同的顏色。
例子：
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;
}
此代碼不正確，因為我正在向集合中添加元素并決定需要多少種顏色。解決這個問題的正確方法是什么
uj5u.com熱心網友回復：
最小顏色數等于單個節點的最大子節點數加一。著色很簡單：用不同的顏色為根和它的孩子著色。然后用不同于父級顏色的顏色為已經著色的子級的子級著色，依此類推。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340384.html