jonowo · October 22, 2021 11:54
diff --git a/random_tree.py b/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)
	"""
	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)