Commit 04f07ae

authored

Merge pull request #3 from Kashyap85/master

Graph and Theory solution for HackerRank

2 parents 7308f20 + 325f12d commit 04f07aeCopy full SHA for 04f07ae

File tree

+23

-0

lines changed

+23

-0

lines changed

Lines changed: 23 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,23 @@`
	`1`	`+from collections import defaultdict`
	`2`	`+def roadsAndLibraries(n, c_lib, c_road, cities):`
	`3`	`+ def dfs(i):`
	`4`	`+ vset.add(i)`
	`5`	`+ ans=1`
	`6`	`+ if i in d:`
	`7`	`+ for j in d[i]:`
	`8`	`+ if j not in vset:`
	`9`	`+ ans+=dfs(j)`
	`10`	`+ return ans`
	`11`	`+`
	`12`	`+ if c_road>c_lib:`
	`13`	`+ return c_lib*n`
	`14`	`+ vset=set()`
	`15`	`+ d=defaultdict(list)`
	`16`	`+ for u,v in cities:`
	`17`	`+ d[u].append(v)`
	`18`	`+ d[v].append(u)`
	`19`	`+ group=[]`
	`20`	`+ for i in range(1,n+1):`
	`21`	`+ if i not in vset:`
	`22`	`+ group.append(dfs(i))`
	`23`	`+ return nc_road+(c_lib-c_road)len(group)`

Comments

(0)