Commit ae989ee

authored

Create Solution.py

1 parent 481bd29 commit ae989eeCopy full SHA for ae989ee

File tree

+26

-0

lines changed

solution/1900-1999/1916.Count Ways to Build Rooms in an Ant Colony
- Solution.py

+26

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+class Solution:`
	`2`	`+ def waysToBuildRooms(self, prevRoom: List[int]) -> int:`
	`3`	`+ modulo = 10**9 + 7`
	`4`	`+ ingoing = defaultdict(set)`
	`5`	`+ outgoing = defaultdict(set)`
	`6`	`+`
	`7`	`+ for i in range(1, len(prevRoom)):`
	`8`	`+ ingoing[i].add(prevRoom[i])`
	`9`	`+ outgoing[prevRoom[i]].add(i)`
	`10`	`+ ans = [1]`
	`11`	`+`
	`12`	`+ def recurse(i):`
	`13`	`+ if len(outgoing[i]) == 0:`
	`14`	`+ return 1`
	`15`	`+`
	`16`	`+ nodes_in_tree = 0`
	`17`	`+ for v in outgoing[i]:`
	`18`	`+ cn = recurse(v)`
	`19`	`+ if nodes_in_tree != 0:`
	`20`	`+ ans[0] *= comb(nodes_in_tree + cn, cn)`
	`21`	`+ ans[0] %= modulo`
	`22`	`+ nodes_in_tree += cn`
	`23`	`+ return nodes_in_tree + 1`
	`24`	`+`
	`25`	`+ recurse(0)`
	`26`	`+ return ans[0] % modulo`

Comments

(0)