Given a tree with N nodes. The task is to color the tree with the minimum number of colors(K) such that the colors of the edges incident to a vertex are different. Print K in first-line and then in next line print N – 1 space-separated integer represents the colors of the edges. Examples:
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
Approach: First, let’s think about the minimum number of colors K. For every vertex v, deg(v) ? K should meet (where deg(v) denotes the degree of vertex v). In fact, there exists a vertex with all K different colors. First, choose a vertex and let it be the root, thus T will be a rooted tree. Perform a breadth-first search from the root. For each vertex, determine the colors of edges between its children one by one. For each edge, use the color with the minimum index among those which are not used as colors of edges whose one of endpoints is the current vertex. Then each index of color does not exceed K. Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Add an edge between the vertexesvoid 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 differentint 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 codeint 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;} |
Java
//Java program for the above approachimport java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.TreeMap;public class Main { // Add an edge between the vertexes public static void addEdge(List<List<Integer>> gr, int x, int y, List<int[]> edges) { gr.get(x).add(y); gr.get(y).add(x); edges.add(new int[] { 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 public static void colorTree(int n, List<List<Integer>> gr, List<int[]> edges) { // To store the minimum colors int K = 0; // To store color of the edges Map<int[], Integer> color = new TreeMap<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // Color of edge between its parent int[] cs = new int[n]; // To check if the vertex is // visited or not boolean[] used = new boolean[n]; Queue<Integer> que = new LinkedList<>(); used[0] = true; que.offer(0); while (!que.isEmpty()) { // Take first element of the queue int v = que.poll(); // Take the possible value of K if (K < gr.get(v).size()) { K = gr.get(v).size(); } // Current color int cur = 1; for (int u : gr.get(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.put(new int[] { u, v }, cur) == null ? cur : color.get(new int[] { u, v }); color.put(new int[] { v, u }, cs[u]); cur++; // Mark it visited used[u] = true; // Push into the queue que.offer(u); } } // Print the minimum required colors System.out.println(K); // Print the edge colors for (int[] p : edges) { System.out.print(color.get(p) + " "); } } // Driver code public static void main(String[] args) { int n = 8; List<List<Integer>> gr = new ArrayList<>(); for (int i = 0; i < n; i++) { gr.add(new ArrayList<>()); } List<int[]> edges = new ArrayList<>(); // Add edges addEdge(gr, 0, 1, edges); addEdge(gr, 1, 2, edges); addEdge(gr, 1, 3, edges); addEdge(gr, 1, 4, edges); addEdge(gr, 3, 6, edges); addEdge(gr, 4, 5, edges); addEdge(gr, 5, 7, edges); // Function call colorTree(n, gr, edges); }}//This code is contributed by Potta Lokesh |
Python
# Python3 implementation of the approachfrom collections import deque as queuegr = [[] for i in range(100)]edges = []# Add an edge between the vertexesdef 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 differentdef 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 coden = 8# Add edgesadd_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 callcolor_tree(n)# This code is contributed by mohit kumar 29 |
C#
using System;using System.Collections.Generic;class Program{ // Add an edge between the vertexes static void AddEdge(List<List<int>> gr, int x, int y, List<Tuple<int, int>> edges) { gr[x].Add(y); gr[y].Add(x); edges.Add(Tuple.Create(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 static int ColorTree(int n, List<List<int>> gr, List<Tuple<int, int>> edges) { // To store the minimum colors int K = 0; // To store color of the edges Dictionary<Tuple<int, int>, int> color = new Dictionary<Tuple<int, int>, int>(); // Color of edge between its parent List<int> cs = new List<int>(new int[n]); // To check if the vertex is visited or not List<int> used = new List<int>(new int[n]); Queue<int> que = new Queue<int>(); used[0] = 1; que.Enqueue(0); while (que.Count > 0) { // Take first element of the queue int v = que.Dequeue(); // Take the possible value of K if (K < gr[v].Count) K = gr[v].Count; // Current color int cur = 1; foreach (int u in gr[v]) { // If vertex is already visited if (used[u] != 0) continue; // If the color is similar to it's parent if (cur == cs[v]) cur++; // Assign the color cs[u] = color[Tuple.Create(u, v)] = color[Tuple.Create(v, u)] = cur++; // Mark it visited used[u] = 1; // Push into the queue que.Enqueue(u); } } // Print the minimum required colors Console.WriteLine(K); // Print the edge colors foreach (Tuple<int, int> p in edges) Console.Write(color[p] + " "); return K; } // Driver code static void Main() { int n = 8; List<List<int>> gr = new List<List<int>>(); for (int i = 0; i < n; i++) gr.Add(new List<int>()); List<Tuple<int, int>> edges = new List<Tuple<int, int>>(); // Add edges AddEdge(gr, 0, 1, edges); AddEdge(gr, 1, 2, edges); AddEdge(gr, 1, 3, edges); AddEdge(gr, 1, 4, edges); AddEdge(gr, 3, 6, edges); AddEdge(gr, 4, 5, edges); AddEdge(gr, 5, 7, edges); // Function call ColorTree(n, gr, edges); }} |
Javascript
// Add an edge between the vertexesfunction add_edge(gr, x, y, edges) { gr[x].push(y); gr[y].push(x); edges.push([x, y]);}// Function to color the tree with minimum// number of colors such that the colors of// the edges incident to a vertex are differentfunction color_tree(n, gr, edges) { // To store the minimum colors let K = 0; // To store color of the edges const color = new Map(); // Color of edge between its parent const cs = new Array(n).fill(0); // To check if the vertex is // visited or not const used = new Array(n).fill(false); const que = []; used[0] = true; que.push(0); while (que.length > 0) { // Take first element of the queue const v = que.shift(); // Take the possible value of K if (K < gr[v].length) { K = gr[v].length; } // Current color let cur = 1; for (const u of gr[v]) { // If vertex is already visited if (used[u]) { continue; } // If the color is similar to its parent if (cur === cs[v]) { cur++; } // Assign the color const edge = [u, v].sort(); color.set(edge.toString(), cur); cs[u] = cur++; // Mark it visited used[u] = true; // Push into the queue que.push(u); } } // Print the minimum required colors console.log(K); // Print the edge colors for (const p of edges) { console.log(color.get(p.sort().toString())); }}// Driver codefunction main() { const n = 8; const gr = new Array(n).fill(null).map(() => []); const 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);}main(); |
Output:
4 1 2 3 4 1 1 2
The time complexity : O(n + e), where n is the number of vertices in the graph and e is the number of edges. This is because the code uses BFS to traverse the graph and visits each vertex and its edges once, which takes O(n + e) time.
The space complexity : O(n + e), as it uses a queue and an array to store vertices, a map to store colors of edges, and an array to store colors of edges between the parent and the vertex.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
