Commitf72c149

authored

Merge pull requestneetcode-gh#374 from ironnicko/main

Added Python Code for Number of Connected Components In An Undirected…

2 parentsaa43937 +4a8cade commitf72c149Copy full SHA for f72c149

File tree

+31

-0

lines changed

+31

-0

lines changed

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,31 @@`
	`1`	`+`
	`2`	`+classSolution:`
	`3`	`+defcount_components(self,n:int,edges:List[List[int]])->int:`
	`4`	`+parent= [iforiinrange(n)]`
	`5`	`+rank= [1]*n`
	`6`	`+`
	`7`	`+deffind_union(node:int)->None:`
	`8`	`+result=node`
	`9`	`+whileresult!=parent[result]:`
	`10`	`+parent[result]=parent[parent[result]]# path compression`
	`11`	`+result=parent[result]`
	`12`	`+returnresult`
	`13`	`+`
	`14`	`+defunion(node_1:int,node_2:int):`
	`15`	`+parent_1=find_union(node_1)`
	`16`	`+parent_2=find_union(node_2)`
	`17`	`+ifparent_1==parent_2:`
	`18`	`+return0`
	`19`	`+ifrank[parent_2]<rank[parent_1]:`
	`20`	`+parent[parent_1]=parent_2`
	`21`	`+rank[parent_2]+=rank[parent_1]`
	`22`	`+else:`
	`23`	`+parent[parent_2]=parent_1`
	`24`	`+rank[parent_1]+=rank[parent_2]`
	`25`	`+return1`
	`26`	`+`
	`27`	`+result=n`
	`28`	`+fornode_1,node_2inedges:`
	`29`	`+result-=union(node_1,node_2)`
	`30`	`+returnresult`
	`31`	`+`

Comments

(0)