Question

python 3

Write a function that receives an array S representing a disjoint set forest and an integer k and determines if k is a root in S. What is the running time of your function with respect to the size of S? 6. 7. Write a function that receives an array S representing a disjoint set forest and an integer k and determines if k is a leaf in S. What is the running time of your function with respect to the size of S?

Answer 1

Read comments for explanation

#a root will be a node which is a parent of itslf
#in forest S check if S[k]=k or not if yes then k is root

#time complexity of this part is O(1)
def isRoot(S,k):
   if S[k]==k:
       return True
   return False
#leaf is node which is not a parent of itself
#traverse S if a node is found whose parent is k return false
#else return true

#time complexity of this part is O(n) where n is number of nodes
def isLeaf(S,k):
   for i in forest:
       if i==k:
           return False
   return True;
#test
forest=[2,0,2,4,4,5]
#parent of 0 is node 2
print(isRoot(forest,0))
#node 2 is a root
print(isRoot(forest,2))
#node0 is parent of node 1
print(isLeaf(forest,0))
#node 1 is a leaf
print(isLeaf(forest,1))

Terminal t : (95%) ) 22:35 * C Python 3| Chegg.com + ← → https://www.HomeworkLib.com/homework-help/expertquestion Ξ Chegg. Study TEXTBOOK SOLUTIONS EXPERT Q&A Search ython 3 Answered 6. Write a function that receives an array S representing a disjoint set forest and an integer k and determines if k isa root in S. What is the running time of your function with respect to the size of S? CF Score NA 100% NA . Write a function that reccives an array S representing a disjoint set forest and an integer k and determines if k is a leaf in S. What is the running time of your function with respect to the size of S? e ayush@ayush-Lenovo-G50-80: Skip to next question ayush@ayush-Lenovo-G50-80: ayush@ayush-Lenovo-G50-80: ayush@ayush-Lenovo-G50-80:-$ False rue False True ayushQayush-Lenovo-G50-80:5 python3 HomeworkLib.py Your answer ! return False return True #test torest-[2.0,2,4,4,5] #parent of o is node 2 print(熙00t(forest,0)) #node 2 is a root printlsRoot(torest,2) #noom is parent of node l printilsl eat torest,0) #node 1 is a leaf print(isleattorest. 1))


HomeworkLib.py ()-gedit t : ) (9696) 22:37 * OpenH Save 1#a root will be a node which is a parent of itslf 2 #tn forest s check if S[k] k or not if yes then k is root 3 #tine complexity of this part is 0(1) 4 def isRoot (S,k): return True return False 8#leaf is node which is not a parent of itself #traverse S if a node is found whose parent is k return false 10#else return true 11 #tine complexity of this part is 0(n) where n is number of nodes 12 def isLeaf(S,k): 13 for i in forest: if i--k: return False 16 17 #test 18 forest-[2,0,2,4,4,5] 19#parent of is node 2 20 print (isRoot(forest,e)) 21#node 2 is a root 22 print(isRoot(forest,2)) 23 #node0 is parent of node 1 24 print (isLeaf(forest,e)) 25#node 1 is a leaf 26 print(tsLeaf(forest,1)) return True; Saving file'/home/ayush/HomeworkLib.py Python Tab Width:4 Ln 11, Col 65 INS