Write a program to input a Prufer sequence and output the un

Write a program to input a Prufer sequence and output the unique tree for that sequence. Your program should input the sequence on standard input (do not use command line arguments or input from a file). Assume the input will be space-separated numbers. The output should be in the unweighted graph format we have been using this semester, except with vertices numbered 1 to n rather than 0 to n-1. The output should look very similar to the following.

Solution

Hi I used algorithm given here https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence. If some other algorithm is taught please share.

import sys

def convertPruferToTree(a):
n = len(a)
t = [i+1 for i in range(0, n+2)]
deg = [0] * len(t)

for i in t:
deg[i-1] = 1

for i in a:
deg[i-1] = deg[i-1] + 1
res = []

for i in a:
for j in t:
if deg[j-1] == 1:
res.append([i,j])
deg[i-1] = deg[i-1] -1
deg[j-1] = deg[j-1] - 1
break
u = 0
v = 0

for i in t:
if deg[i-1] == 1:
deg[i-1] = deg[i-1] - 1
if u == 0:
u = i
else:
v = i
break

res.append([u,v])

for i in res:
print i[0],\"\\t\",i[1]

a = sys.argv[1:]
a = [int(i) for i in a]

convertPruferToTree(a)
  

#pastebin link : http://pastebin.com/aTAM0Pt2