CSES Solutions – Prüfer Code
A Prüfer code of a tree of n nodes is a sequence of n-2 integers that uniquely specifies the structure of the tree. The code is constructed as follows: As long as there are at least three nodes left, find a leaf with the smallest label, add the label of its only neighbor to the code, and remove the leaf from the tree. Given a Prüfer code of a tree, your task is to construct the original tree .
Examples:
Input : n = 5, prufer code = 2 2 4
Output:
1 2
2 3
2 4
4 5
Explanation : The Prüfer code {2, 2, 4} builds a tree with leaves connecting to node 2 (1-2, 2-3, 2-4), and the remaining node (4) connects to the last leaf (4-5) for a total of 4 edges.Input : n = 6, prufer code = 1 3 3 1
Output : Edges : 2-1 , 4 -3, 5-3, 3 -1, 1- 6
Explanation : The Prüfer code {1, 3, 3, 1} reveals connections for leaves (2-1, 4-3, 5-3), reconstructing the tree with remaining nodes (3-1, 1-6) for a total of 5 edges.
Approach: To solve the problem, follow the below idea:
Prufer Code provides a unique code for every tree. Each tree can have only one Prufer code and each Prufer Code can map to exactly one Tree.
Imagine you have a secret code that tells you how to build a tree, but it only mentions connections for leafy branches (ones with just one connection). That’s kind of how a Prüfer code works.
While generating the Prufer Code, we always add the neighbor of the leaf node to the Prufer Code. So, we know that all the nodes, which are not present in the Prufer Code are leaves of the tree. So, now we can start constructing out tree from the leaf nodes.
- Degree of all nodes in the Prufer Code: All the nodes which are not present in the Prufer Code are leaf nodes and have degree = 0.
- Start from the leaves: Start from the leaf node, and add an edge between first node of the Prufer Code and the leaf node.
- Decrease the degree of the nodes: Decrease the degree of the first node of the Prufer Code and the leaf node. If the degree of nodes become less than 0, then it means that those nodes will no longer form any edge with any node. If the degree of node becomes 0, then it means we can consider it as a leaf node to form edges with another node.
- Move to the next node in the Prufer Code: Move to the next node in the Prufer Code and make an edge with this node and the smallest node which has indegree of 0.
- Repeat for the remaining nodes: Repeat the above step till all the nodes of the Prufer Code are finished.
- Last Two Nodes: After all the nodes of Prufer Code are covered, then there will be 2 nodes left with degree = 0. Add an edge between those two nodes to construct the final graph.
Step-by-step algorithm:
- Maintain a set, say availableNodes to store the potential leaves of the tree.
- Push all the nodes in the availableNodes.
- Remove the nodes which are in the PruferCode from availableNodes as they can never be leaf nodes.
- Iterate over all the elements of PruferCode,
- For any node at index i, PruferCode[i] find the smallest leaf node from availableNodes and print the edge between PruferCode[i] and smallest leaf.
- Remove the smallest leaf from the availableNodes.
- Decrease the degree of node PruferCode[i] and push it in availableNodes if its degree becomes 0.
- Get the remaining two nodes from the set availableNodes.
- Print the last edge connecting these two nodes.
Below is the implementation of the above algorithm:
#include <bits/stdc++.h> // Include necessary headers (may need adjustment)
using namespace std;
int main()
{
// Sample Input
long long n = 6;
// Vector to store the Prüfer code (length n-2)
vector<long long> pruferCode(n - 2);
pruferCode = { 1, 3, 3, 1 }; // Example prufer code
// Set to store available node labels (initially all
// nodes from 1 to n)
set<long long> availableNodes;
for (long long i = 1; i <= n; i++) {
availableNodes.insert(i);
}
// Array to store the degree (number of connections) of
// each node (size n+1, initialized to 0)
long long degrees[n + 1] = { 0 };
// Process the Prüfer code and update degrees
for (auto element : pruferCode) {
// Increase degree of the node mentioned in the code
degrees[element]++;
// If the node exists in available nodes (potential
// leaf), remove it
if (availableNodes.count(element)) {
availableNodes.erase(element);
}
}
// Construct the tree edges iteratively
for (long long i = 0; i < n - 2; i++) {
// Get the first element (smallest label) from
// available nodes (represents a leaf)
long long leafNode = *availableNodes.begin();
availableNodes.erase(leafNode);
// Print the edge: leaf node connects to the node
// from the code
cout << leafNode << " " << pruferCode[i] << endl;
// Decrement the degree of the connected node
degrees[pruferCode[i]]--;
// If the connected node becomes a leaf (degree 0),
// add it back to available nodes
if (degrees[pruferCode[i]] == 0) {
availableNodes.insert(pruferCode[i]);
}
}
// Connect the last two nodes (remaining elements in
// available nodes)
cout << *availableNodes.begin() << " "
<< *availableNodes.rbegin();
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args)
{
// Sample Input
long n = 6;
// ArrayList to store the Prüfer code (length n-2)
ArrayList<Long> pruferCode
= new ArrayList<>(Arrays.asList(
1L, 3L, 3L, 1L)); // Example prufer code
// Set to store available node labels (initially all
// nodes from 1 to n)
TreeSet<Long> availableNodes = new TreeSet<>();
for (long i = 1; i <= n; i++) {
availableNodes.add(i);
}
// Array to store the degree (number of connections)
// of each node (size n+1, initialized to 0)
long[] degrees = new long[(int)(n + 1)];
// Process the Prüfer code and update degrees
for (long element : pruferCode) {
// Increase degree of the node mentioned in the
// code
degrees[(int)element]++;
// If the node exists in available nodes
// (potential leaf), remove it
if (availableNodes.contains(element)) {
availableNodes.remove(element);
}
}
// Construct the tree edges iteratively
for (int i = 0; i < n - 2; i++) {
// Get the first element (smallest label) from
// available nodes (represents a leaf)
long leafNode = availableNodes.first();
availableNodes.remove(leafNode);
// Print the edge: leaf node connects to the
// node from the code
System.out.println(leafNode + " "
+ pruferCode.get(i));
// Decrement the degree of the connected node
degrees[pruferCode.get(i).intValue()]--;
// If the connected node becomes a leaf (degree
// 0), add it back to available nodes
if (degrees[pruferCode.get(i).intValue()]
== 0) {
availableNodes.add(pruferCode.get(i));
}
}
// Connect the last two nodes (remaining elements in
// available nodes)
System.out.println(availableNodes.first() + " "
+ availableNodes.last());
}
}
# Sample Input
n = 6
# List to store the Prüfer code (length n-2)
prufer_code = [1, 3, 3, 1] # Example prufer code
# Set to store available node labels (initially all nodes from 1 to n)
available_nodes = set(range(1, n + 1))
# Dictionary to store the degree (number of connections) of each node
degrees = {i: 0 for i in range(1, n + 2)}
# Process the Prüfer code and update degrees
for element in prufer_code:
# Increase degree of the node mentioned in the code
degrees[element] += 1
# If the node exists in available nodes (potential leaf), remove it
if element in available_nodes:
available_nodes.remove(element)
# Construct the tree edges iteratively
for i in range(n - 2):
# Get the first element (smallest label) from available nodes (represents a leaf)
leaf_node = min(available_nodes)
available_nodes.remove(leaf_node)
# Print the edge: leaf node connects to the node from the code
print(leaf_node, prufer_code[i])
# Decrement the degree of the connected node
degrees[prufer_code[i]] -= 1
# If the connected node becomes a leaf (degree 0), add it back to available nodes
if degrees[prufer_code[i]] == 0:
available_nodes.add(prufer_code[i])
# Connect the last two nodes (remaining elements in available nodes)
print(min(available_nodes), max(available_nodes))
# This code is contributed by Ayush Mishra
// Sample Input
let n = 6;
// Array to store the Prüfer code (length n-2)
let pruferCode = [1, 3, 3, 1]; // Example prufer code
// Set to store available node labels (initially all nodes from 1 to n)
let availableNodes = new Set();
for (let i = 1; i <= n; i++) {
availableNodes.add(i);
}
// Array to store the degree (number of connections) of each node (size n+1, initialized to 0)
let degrees = new Array(n + 1).fill(0);
// Process the Prüfer code and update degrees
pruferCode.forEach(element => {
// Increase degree of the node mentioned in the code
degrees[element]++;
// If the node exists in available nodes (potential leaf), remove it
if (availableNodes.has(element)) {
availableNodes.delete(element);
}
});
// Construct the tree edges iteratively
for (let i = 0; i < n - 2; i++) {
// Get the first element (smallest label) from available nodes (represents a leaf)
let leafNode = availableNodes.values().next().value;
availableNodes.delete(leafNode);
// Log the edge: leaf node connects to the node from the code
console.log(leafNode + " " + pruferCode[i]);
// Decrement the degree of the connected node
degrees[pruferCode[i]]--;
// If the connected node becomes a leaf (degree 0), add it back to available nodes
if (degrees[pruferCode[i]] === 0) {
availableNodes.add(pruferCode[i]);
}
}
// Connect the last two nodes (remaining elements in available nodes)
console.log(Array.from(availableNodes).join(" "));
// This code is contributed by hthakuqfon
Output
2 1 4 3 5 3 3 1 1 6
Time Complexity: O(N * logN), where N is the number of nodes in the graph.
Auxiliary Space: O(N)