Generate a random tree with n nodes using a Prüfer sequence.

random_tree.py

"""
Generate a random tree with n nodes using a Prüfer sequence.
Can be used for creating test cases in competitive programming.

Time complexity: O(n^2)
Algorithm: https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
"""

import random

# Nodes are numbered 1 - n
n = 100

prufer_seq = [random.randint(1, n) for _ in range(n - 2)]
edges = []
deg = [1] * (n + 1)
for i in prufer_seq:
    deg[i] += 1

for i in prufer_seq:
    for j in range(1, n + 1):
        if deg[j] == 1:
            edges.append([i, j])
            deg[i] -= 1
            deg[j] -= 1
            break
# Last edge
u, v = [i for i in range(1, n + 1) if deg[i] == 1]
edges.append([u, v])

# Randomize edges
random.shuffle(edges)
for i in range(n - 1):
    random.shuffle(edges[i])

for u, v in edges:
    print(u, v)