Given three integers N, D and K. The task is to check whether it is possible to make a tree with exactly N vertices, D diameter (the number of edges in the longest path between any two vertices), and degree of each vertex must be at most K. If it is possible then print all the possible edges otherwise print No.
Examples:
Input: N = 6, D = 3, K = 4
Output:
1 2
2 3
3 4
5 2
6 2
Input: N = 6, D = 2, K = 4
Output: N0
Approach: Let’s construct the tree with the following algorithm: If (d > n – 1), print “No” and terminate the program. Otherwise, let’s keep the array deg of the length n which will represent degrees of vertices.
The first step is to construct the diameter of the tree. Let the first (d + 1) vertices form it.
Let’s add d edges to the answer and increase degrees of vertices corresponding to these edges, and if some vertex has degree greater than k, print “No” and terminate the program.
The second (and the last) step is to attach the remaining (n – d – 1) vertices to the tree. Let’s call the vertex free if its degree is less than k. Also, let’s keep all free vertices forming the diameter in some data structure which allows us to take the vertex with the minimum maximal distance to any other vertex and remove such vertices. It can be done by, for example, set of pairs (distv, v), where distv is the maximum distance from the vertex v to any other vertex. Now let’s add all the vertices starting from the vertex (d + 1) (0-indexed) to the vertex n?1, let the current vertex be u. One can get the vertex with the minimum maximal distance to any other vertex, let it be v. Now increase the degree of vertices u and v, add the edge between them, and if v still be free, return it to the data structure, otherwise remove it. The same with the vertex u (it is obvious that its maximal distance to any other vertex will be equal to (distv + 1).
If at any step our data structure will be empty or the minimum maximal distance will equal d, the answer is “No”. Otherwise, we can print the answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to Make a tree with n vertices, d as it's // diameter and degree of each vertex is at most k void Make_tree(int n, int d, int k) { // If diameter > n - 1 // impossible to build tree if (d > n - 1) { cout << "No"; return; } // To store the degree of each vertex vector<int> deg(n); // To store the edge between vertices vector<pair<int, int> > ans; // To store maximum distance among // all the paths from a vertex set<pair<int, int> > q; // Make diameter of tree equals to d for (int i = 0; i < d; ++i) { ++deg[i]; ++deg[i + 1]; if (deg[i] > k || deg[i + 1] > k) { cout << "NO" << endl; return; } // Add an edge between them ans.push_back(make_pair(i, i + 1)); } // Store maximum distance of each vertex // from other vertices for (int i = 1; i < d; ++i) q.insert(make_pair(max(i, d - i), i)); // For next (n - d - 1) edges for (int i = d + 1; i < n; ++i) { // If the vertex already has the degree k while (!q.empty() && deg[q.begin()->second] == k) q.erase(q.begin()); // If not possible if (q.empty() || q.begin()->first == d) { cout << "No"; return; } // Increase the degree of vertices ++deg[i]; ++deg[q.begin()->second]; // Add an edge between them ans.push_back(make_pair(i, q.begin()->second)); // Store the maximum distance of this vertex // from other vertices q.insert(make_pair(q.begin()->first + 1, i)); } // Print all the edges of the built tree for (int i = 0; i < n - 1; ++i) cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl; } // Driver code int main() { int n = 6, d = 3, k = 4; Make_tree(n, d, k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class Main { // Function to Make a tree with n vertices, d as its diameter // and degree of each vertex is at most k static void Make_tree(int n, int d, int k) { // If diameter > n - 1 // impossible to build tree if (d > n - 1) { System.out.println("No"); return; } // To store the degree of each vertex int[] deg = new int[n]; // To store the edge between vertices ArrayList<int[]> ans = new ArrayList<int[]>(); // To store maximum distance among all the paths from a vertex HashMap<int[], Integer> q = new HashMap<int[], Integer>(); // Make diameter of tree equals to d for (int i = 0; i < d; i++) { deg[i]++; deg[i + 1]++; if (deg[i] > k || deg[i + 1] > k) { System.out.println("No"); return; } // Add an edge between them int[] edge = {i, i + 1}; ans.add(edge); } // Store maximum distance of each vertex from other vertices for (int i = 1; i < d; i++) { int[] key = {Math.max(i, d - i), i}; q.put(key, 1); } // For next (n - d - 1) edges for (int i = d + 1; i < n; i++) { ArrayList<int[]> arr = new ArrayList<int[]>(q.keySet()); // If the vertex already has the degree k while (q.size() > 0 && deg[arr.get(0)[1]] == k) { q.remove(arr.get(0)); arr.remove(0); } // If not possible if (q.size() == 0 || arr.get(0)[0] == d) { System.out.println("No"); return; } // Increase the degree of vertices deg[i]++; deg[arr.get(0)[1]]++; // Add an edge between them int[] edge = {i, arr.get(0)[1]}; ans.add(edge); // Store the maximum distance of this vertex from other vertices int[] key = {arr.get(0)[0] + 1, i}; q.put(key, 1); } // Print all the edges of the built tree for (int i = 0; i < n - 1; i++) { System.out.println((ans.get(i)[0] + 1) + " " + (ans.get(i)[1] + 1)); } } // Driver code public static void main(String[] args) { int n = 6, d = 3, k = 4; Make_tree(n, d, k); } } |
Python3
# Python3 implementation of the approach # Function to Make a tree with n vertices, d as it's # diameter and degree of each vertex is at most k def Make_tree(n, d, k): # If diameter > n - 1 # impossible to build tree if (d > n - 1): print("No") return # To store the degree of each vertex deg = [0]*(n) # To store the edge between vertices ans = [] # To store maximum distance among #all the paths from a vertex q = {} # Make diameter of tree equals to d for i in range(d): deg[i] += 1 deg[i + 1] += 1 if (deg[i] > k or deg[i + 1] > k): print("NO") return # Add an edge between them ans.append((i, i + 1)) # Store maximum distance of each vertex # from other vertices for i in range(1, d): q[(max(i, d - i), i)] = 1 # For next (n - d - 1) edges for i in range(d + 1, n): arr = list(q.keys()) # If the vertex already has the degree k while (len(q) > 0 and deg[arr[0][1]] == k): del q[arr[0]] # If not possible if (len(q) == 0 or arr[0][0] == d): print ("No") return # Increase the degree of vertices deg[i] += 1 deg[arr[0][1]] += 1 # Add an edge between them ans.append((i, arr[0][1])) # Store the maximum distance of this vertex # from other vertices q[(arr[0][0] + 1, i)] = 1 # Print all the edges of the built tree for i in range(n - 1): print(ans[i][0] + 1, ans[i][1]+ 1) # Driver code if __name__ == '__main__': n, d, k = 6, 3, 4 Make_tree(n, d, k) # This code is contributed by mohit kumar 29. |
C#
//C# code for the above approach using System; using System.Collections.Generic; class MainClass { public static void MakeTree(int n, int d, int k) { // If diameter > n - 1 // impossible to build tree if (d > n - 1) { Console.WriteLine("No"); return; } // To store the degree of each vertex List<int> deg = new List<int>(new int[n]); // To store the edge between vertices List<Tuple<int, int>> ans = new List<Tuple<int, int>>(); // To store maximum distance among // all the paths from a vertex SortedSet<Tuple<int, int>> q = new SortedSet<Tuple<int, int>>(); // Make diameter of tree equals to d for (int i = 0; i < d; ++i) { ++deg[i]; ++deg[i + 1]; if (deg[i] > k || deg[i + 1] > k) { Console.WriteLine("NO"); return; } // Add an edge between them ans.Add(Tuple.Create(i, i + 1)); } // Store maximum distance of each vertex // from other vertices for (int i = 1; i < d; ++i) q.Add(Tuple.Create(Math.Max(i, d - i), i)); // For next (n - d - 1) edges for (int i = d + 1; i < n; ++i) { // If the vertex already has the degree k while (q.Count > 0 && deg[q.Min.Item2] == k) q.Remove(q.Min); // If not possible if (q.Count == 0 || q.Min.Item1 == d) { Console.WriteLine("No"); return; } // Increase the degree of vertices ++deg[i]; ++deg[q.Min.Item2]; // Add an edge between them ans.Add(Tuple.Create(i, q.Min.Item2)); // Store the maximum distance of this vertex // from other vertices q.Add(Tuple.Create(q.Min.Item1 + 1, i)); } // Print all the edges of the built tree for (int i = 0; i < n - 1; ++i) Console.WriteLine(ans[i].Item1 + 1 + " " + (ans[i].Item2 + 1)); } public static void Main(string[] args) { int n = 6, d = 3, k = 4; MakeTree(n, d, k); } } //This code is contributed by Potta Lokesh |
Javascript
<script> // Javascript implementation of the approach // Function to Make a tree with n vertices, // d as it's diameter and degree of each // vertex is at most k function Make_tree(n, d, k) { // If diameter > n - 1 // impossible to build tree if (d > n - 1) { document.write("No"); return; } // To store the degree of each vertex let deg = new Array(n); for(let i = 0; i < n; i++) { deg[i] = 0; } // To store the edge between vertices let ans = []; // To store maximum distance among // all the paths from a vertex let q = new Set(); // Make diameter of tree equals to d for(let i = 0; i < d; ++i) { ++deg[i]; ++deg[i + 1]; if (deg[i] > k || deg[i + 1] > k) { document.write("NO<br>"); return; } // Add an edge between them ans.push([i, i + 1]); } // Store maximum distance of each vertex // from other vertices for(let i = 1; i < d; ++i) q.add([(Math.max(i, d - i), i)]); // For next (n - d - 1) edges for(let i = d + 1; i < n; ++i) { let arr = Array.from(q); // If the vertex already has the degree k while (q.size != 0 && deg[arr[0][1]] == k) q.delete(arr[0]); // If not possible if (q.size == 0 || arr[0][0] == d) { document.write("No<br>") return; } // Increase the degree of vertices ++deg[i]; ++deg[arr[0][1]]; // Add an edge between them ans.push([i, arr[0][1]]); // Store the maximum distance of this // vertex from other vertices q.add([arr[0][0] + 1, i]); } // Print all the edges of the built tree for(let i = 0; i < n - 1; ++i) document.write((ans[i][0] + 1) + " " + (ans[i][1] + 1) + "<br>"); } // Driver code let n = 6, d = 3, k = 4; Make_tree(n, d, k); // This code is contributed by unknown2108 </script> |
Output:
1 2 2 3 3 4 5 2 6 2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
