Árbol de colores con colores mínimos tales que los colores de las aristas que inciden en un vértice son diferentes

Dado un árbol con N Nodes. La tarea es colorear el árbol con el mínimo número de colores ( K ) tal que los colores de las aristas que inciden en un vértice sean diferentes. Imprima K en la primera línea y luego en la siguiente línea, imprima N: 1 entero separado por espacios representa los colores de los bordes.

Ejemplos:

Input: N = 3, edges[][] = {{0, 1}, {1, 2}}
                   0
                  /  
                 1
                /
               2  
Output:
2
1 2
                   0
                  / (1) 
                 1
                / (2)
               2

Input: N = 8, edges[][] = {{0, 1}, {1, 2}, 
                           {1, 3}, {1, 4}, 
                           {3, 6}, {4, 5}, 
                           {5, 7}}
                    0
                   /
                  1
                / \ \
               2   3 4
                  /   \
                 6     5
                        \
                         7
Output:
4
1 2 3 4 1 1 2

Enfoque: Primero, pensemos en el número mínimo de colores K . Para cada vértice v , debe cumplir grado(v) ≤ K (donde grado(v) denota el grado del vértice v ). De hecho, existe un vértice con todos los K colores diferentes. Primero, elige un vértice y deja que sea la raíz, así T será un árbol con raíz. Realice una búsqueda primero en amplitud desde la raíz. Para cada vértice, determine los colores de los bordes entre sus hijos uno por uno. Para cada borde, use el color con el índice mínimo entre los que no se usan como colores de bordes cuyo uno de los extremos es el vértice actual. Entonces cada índice de color no excede K.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Add an edge between the vertexes
void add_edge(vector<vector<int> >& gr, int x,
              int y, vector<pair<int, int> >& edges)
{
    gr[x].push_back(y);
    gr[y].push_back(x);
    edges.push_back({ x, y });
}
  
// Function to color the tree with minimum
// number of colors such that the colors of
// the edges incident to a vertex are different
int color_tree(int n, vector<vector<int> >& gr,
               vector<pair<int, int> >& edges)
{
  
    // To store the minimum colors
    int K = 0;
  
    // To store color of the edges
    map<pair<int, int>, int> color;
  
    // Color of edge between its parent
    vector<int> cs(n, 0);
  
    // To check if the vertex is
    // visited or not
    vector<int> used(n, 0);
  
    queue<int> que;
    used[0] = 1;
    que.emplace(0);
  
    while (!que.empty()) {
  
        // Take first element of the queue
        int v = que.front();
        que.pop();
  
        // Take the possible value of K
        if (K < (int)gr[v].size())
            K = gr[v].size();
  
        // Current color
        int cur = 1;
  
        for (int u : gr[v]) {
  
            // If vertex is already visited
            if (used[u])
                continue;
  
            // If the color is similar
            // to it's parent
            if (cur == cs[v])
                cur++;
  
            // Assign the color
            cs[u] = color[make_pair(u, v)]
                = color[make_pair(v, u)] = cur++;
  
            // Mark it visited
            used[u] = 1;
  
            // Push into the queue
            que.emplace(u);
        }
    }
  
    // Print the minimum required colors
    cout << K << endl;
  
    // Print the edge colors
    for (auto p : edges)
        cout << color[p] << " ";
}
  
// Driver code
int main()
{
    int n = 8;
  
    vector<vector<int> > gr(n);
    vector<pair<int, int> > edges;
  
    // Add edges
    add_edge(gr, 0, 1, edges);
    add_edge(gr, 1, 2, edges);
    add_edge(gr, 1, 3, edges);
    add_edge(gr, 1, 4, edges);
    add_edge(gr, 3, 6, edges);
    add_edge(gr, 4, 5, edges);
    add_edge(gr, 5, 7, edges);
  
    // Function call
    color_tree(n, gr, edges);
  
    return 0;
}

# Python3 implementation of the approach
from collections import deque as queue
  
gr = [[] for i in range(100)]
edges = []
  
# Add an edge between the vertexes
def add_edge(x, y):
    gr[x].append(y)
    gr[y].append(x)
    edges.append([x, y])
  
# Function to color the tree with minimum
# number of colors such that the colors of
# the edges incident to a vertex are different
def color_tree(n):
  
    # To store the minimum colors
    K = 0
  
    # To store color of the edges
    color = dict()
  
    # Color of edge between its parent
    cs = [0] * (n)
  
    # To check if the vertex is
    # visited or not
    used = [0] * (n)
  
    que = queue()
    used[0] = 1
    que.append(0)
  
    while (len(que) > 0):
  
        # Take first element of the queue
        v = que.popleft()
  
        # Take the possible value of K
        if (K < len(gr[v])):
            K = len(gr[v])
  
        # Current color
        cur = 1
  
        for u in gr[v]:
  
            # If vertex is already visited
            if (used[u]):
                continue
  
            # If the color is similar
            # to it's parent
            if (cur == cs[v]):
                cur += 1
  
            # Assign the color
            cs[u] = cur
            color[(u, v)] = color[(v, u)] = cur
            cur += 1
  
            # Mark it visited
            used[u] = 1
  
            # Push into the queue
            que.append(u)
  
    # Print minimum required colors
    print(K)
  
    # Print edge colors
    for p in edges:
        i = (p[0], p[1])
        print(color[i], end = " ")
  
# Driver code
n = 8
  
# Add edges
add_edge(0, 1)
add_edge(1, 2)
add_edge(1, 3)
add_edge(1, 4)
add_edge(3, 6)
add_edge(4, 5)
add_edge(5, 7)
  
# Function call
color_tree(n)
  
# This code is contributed by mohit kumar 29

4
1 2 3 4 1 1 2