adding colors to nodes in tree-CodePudding

I have a tree, my task is to find the minimum count of colors needed to color the nodes so that no two children of the same parent share the same color, also parent and child do not share the same color.

Example:

number of edges = 5
root = 1

The edges are:

1 2
1 4
2 3
3 5
4 6

Output:

This is the code which I tried:

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;
}

This code is not correct, as I am adding elements to a set and decide how many colors are needed. What is the correct approach to solve this problem

CodePudding user response：

The minimum number of colors is equal to the maximum number of children of a single node plus one. The coloring is straight forward: color the root and its children with different colors. Then color the children of the already colored children with colors different from their parent's color, and so on.