We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For disjoint sets, I prefer sets over trees. Sets give you O(1) for find and O(n) for union. (Opposite of trees.)
defmaxCircle(queries):# answersans=[]# map nodes to the set they belong tonode_to_set=dict()# by keeping track of the maximum, we save timemaximum=0forqinqueries:# incoming nodesn1,n2=q[0],q[1]# if n1 doesn't exist, create it with its own setifn1notinnode_to_set:node_to_set[n1]=set([n1])# if n2 doesn't exist, create it with its own setifn2notinnode_to_set:node_to_set[n2]=set([n2])# get the setss1,s2=node_to_set[n1],node_to_set[n2]# if nodes share the same set, then no union neededifs1!=s2:# for sake of time, lets set s1 to be the largestiflen(s2)>len(s1):s1,s2=s2,s1# add s2 to s1s1.update(s2)# update all nodes from s2 to now point to s1fornins2:node_to_set[n]=s1# update the maximummaximum=max(len(s1),maximum)# add the answerans.append(maximum)returnans
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Friend Circle Queries
You are viewing a single comment's thread. Return to all comments →
For disjoint sets, I prefer sets over trees. Sets give you O(1) for find and O(n) for union. (Opposite of trees.)