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.
I came to this problem right after the "disjoint sets" problem, in which I learned the DSU data structure and implemented it for that problem.
Interestingly, I started out trying to use my DSU data structure for this problem - but changed approaches to something else (balanced binary search trees) because I neglected to consider an important constraint:
This problem's inputs bg[i][j] are all constrained to be >= 1 <= n * 2. Because I didn't consider this, I didn't see an opportunity to use make on a static set of nodes.
In any event, there are some test cases that cause data structures like a BST to become skewed to worse case - timing me out, which I considered solving with a red-black tree implementation. At that point I suspected I was overcomplicating things, and revisited the idea of using a vanilla DSU for this, at which point it occured to me I could make an initial forest of n * 2 nodes, insert all b[i][j] using union, and ultimately using find on each node to get the size of the connected graphs from the representative of each set.
Here's a python solution that passed the test cases.
"""Solutiontothehackerrank"components in a graph"challengedescribedhere:https://www.hackerrank.com/challenges/components-in-graph/problem?isFullScreen=trueThissolutionusesthe'find'operationafterinertingeachcomponentpairtoobtaintherootofeachsetwhichcontainsthenumberofcomponents."""importosfromtypingimportAny,List,Tuple# a flag to control debug output vs. outpt to be analyzed by # test driver to determine if the output of this program is # correctDEBUG=os.environ.get("HR_DEBUG",0)# call this, not print, to throttle debug outputdefdebug(payload):ifDEBUG:print(payload)classNode:"""Anodehasaparent,valueandsize.Sizerelevantonlyifparent=None(e.g.itistheroot)."""def__init__(self,parent:Any,value:int,size:int):"""Createanode.:paramparent:theparentforthenode.ProbablyNoneinitially.:paramvalue:thevalueforthisnode.:paramsize:thesizeofthisnode.Probably1initially."""self.parent=parentself.value=valueself.size=sizedef__repr__(self):"""Printthisnode'svalueanditsparent(recursive)."""returnf"{self.value+1}->{self.parent}"classDSU:"""AdatasetthatimplementstheDisjointSet-Unionmehods:make(implementedas__init__)findunionforanarbitrarilysizedforest.Assuresamoritizedtimecomplexityusingpathcompressiononfindandparentingthesmallesttreetothelargesttreewhenmergingtwosets.Implementationinspiredbythedisjointsetdiscussionhere:https://en.wikipedia.org/wiki/Disjoint-set_data_structure"""def__init__(self,n:int):"""Initializeaforestwitheachmemberthroughninitsownset.:paramn:thesizeoftheforest."""self.n=nself.tree:List[Node]=[Node(parent=None,value=i,size=1)foriinrange(n)]deffind(self,value:int)->Node:"""Findtherootofthetreeintheforestcontainingthevalue'value'.:paramvalue:valueintheforesttofindtherootfor.Guaranteedtobewithinboundsoftheforest.:return:therootnodeofthetreecontaining'value'."""# if we're the root, this is our representativen:Node=self.tree[value]# debug(f"found {n}")whilen.parent!=None:n=n.parent# compress pathn2:Node=self.tree[value]whilen2.parent:# debug(f"setting {n2.parent} to {n}")saved_parent=n2.parentn2.parent=nn2=saved_parentreturnndefunion(self,i,j):"""Mergetwotreesrepresentedbyvaluesi,j,togetheriftheirrootsarenotthesame.No-opifi,jarerepresentativesofthesametree.Thetreewiththelargestsizebecomestheparentofthetreewiththesmallersize.:parami:thefirstrepresentative.:paramj:thesecondrepresentative."""i_node=self.find(i)j_node=self.find(j)ifj_node==i_node:returnifi_node.size>j_node.size:j_node.parent=i_nodei_node.size+=j_node.sizeelse:i_node.parent=j_nodej_node.size+=i_node.sizedef__repr__(self):"""Printeachnodeineachtreeoftheforest.Recursthroughthenodes."""returnf"{[n for n in self.tree]}"defcounts(dsu:DSU)->Tuple[int,int]:"""Givenadsu,findtherepresentativeofeachsetanddeterminethesmallerandlargestnumberofcomponentsfromthoserepresentatives.:paramdsu:aDisjoint-Set-Uniondatastructurewith'find'operation.:return:largest,smallestintegers."""largest=0smallest=Noneforiindsu.tree:root=dsu.find(i.value)ifroot.size>largest:largest=root.sizeifroot.size>1and(smallestisNoneorroot.size<smallest):smallest=root.sizedebug(root.size)return[smallest,largest]defcomponentsInGraph(gb):"""Fromchallenge:paramgb:seechallengedescription:return:[smallest,largets]-seechallengedescription."""# we get N, and know that i, j fall within 1 <= i, j <= n * 2n=len(gb)debug(f"{n}")# initialize our data structure with the input number of trees this is only# possible because the problem constrains the values for i, j. If that were# not the case, we may need to resort to implementing a red-black tree to# manage insertion of arbitrary nodes into the forest.dsu=DSU(n=n*2)# sanity check that the DSU structure is set up rightdebug(dsu)# handle each queryfori,jingb:# impl detail: -1 because our array is 0-based, but the input is 1 based.dsu.union(i-1,j-1)returncounts(dsu=dsu)if__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')n=int(input().strip())gb=[]for_inrange(n):gb.append(list(map(int,input().rstrip().split())))result=componentsInGraph(gb)fptr.write(' '.join(map(str,result)))fptr.write('\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Components in a graph
You are viewing a single comment's thread. Return to all comments →
I came to this problem right after the "disjoint sets" problem, in which I learned the DSU data structure and implemented it for that problem.
Interestingly, I started out trying to use my DSU data structure for this problem - but changed approaches to something else (balanced binary search trees) because I neglected to consider an important constraint:
This problem's inputs bg[i][j] are all constrained to be >= 1 <= n * 2. Because I didn't consider this, I didn't see an opportunity to use
make
on a static set of nodes.In any event, there are some test cases that cause data structures like a BST to become skewed to worse case - timing me out, which I considered solving with a red-black tree implementation. At that point I suspected I was overcomplicating things, and revisited the idea of using a vanilla DSU for this, at which point it occured to me I could
make
an initial forest of n * 2 nodes, insert all b[i][j] usingunion
, and ultimately usingfind
on each node to get the size of the connected graphs from the representative of each set.Here's a python solution that passed the test cases.