Random Tree Generator

randomTree.py

#!/usr/bin/python
import random
import copy
import collections
import Queue
import sys
T = 7
N = 50000
W1, W2 = 1000, 10000

def genTree(n):
    ret = []
    reservoir = range(1, n+1)
    random.shuffle(reservoir)
    vis = []
    vis.append(reservoir.pop())
    while len(reservoir) != 0:
        u = random.choice(vis)
        v = reservoir.pop()
        ret.append((u, v))
        vis.append(v)

    return ret


def main():
    for i in range(T):
        n = random.randint(2, N)
        m = random.randint(1, n-1)
        tree = genTree(n)
        print len(tree)+1

        for (u, v) in tree:
            print u, v
        
        print m
        reservoir = range(2, n+1)
        random.shuffle(reservoir)
        for i in reservoir[:m]:
            print i

if __name__ == '__main__':
    main()