Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function Template for python3
- class Solution:
- #Function to find sum of weights of edges of the Minimum Spanning Tree.
- def spanningTree(self, n, d):
- def find(u):
- if parent[u]==u:
- parent[u]=u
- return u
- else:
- #path compression
- parent[u]=find(parent[u])
- return parent[u]
- def union(a,b):
- x=find(a)
- y=find(b)
- if x==y:
- return False
- #union by rank
- #if ranks of two nodes are same then rank of unified set will be incremented by 1 else rank remains unchanged
- elif rank[x]==rank[y]:
- rank[y]+=1
- parent[x]=y
- elif rank[x]<rank[y]:
- parent[x]=y
- else:
- parent[y]=x
- return True
- e=[]
- ans=0
- for i in range(n):
- for j,k in d[i]:
- e.append((i,j,k))
- e.sort(key=lambda x:x[2])
- c=0
- #initialisation steps vvimp
- rank=[0]*n
- parent=[i for i in range(n)]
- for a,b,w in e:
- #do process till we get sufficient edges
- if c<n-1:
- #if union ==False means by adding (a,b) results a cycle
- if union(a,b):
- ans+=w
- c+=1
- else:break
- return ans
Add Comment
Please, Sign In to add comment