Advertisement
viligen

salaries_dfs

Aug 9th, 2022
515
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.67 KB | None | 0 0
  1. def dfs(node, graph, salaries):
  2.     if salaries[node] is not None:
  3.         return salaries[node]
  4.     if len(graph[node]) == 0:
  5.         salaries[node] = 1
  6.         return 1
  7.     salary = 0
  8.     for child in graph[node]:
  9.         salary += dfs(child, graph, salaries)
  10.     salaries[node] = salary
  11.     return salary
  12.  
  13.  
  14. nodes = int(input())
  15.  
  16. graph = []
  17.  
  18. for _ in range(nodes):
  19.     line = input()
  20.     children = []
  21.     for idx, state in enumerate(line):
  22.         if line[idx] == 'Y':
  23.             children.append(idx)
  24.     graph.append(children)
  25.  
  26. salaries = [None] * nodes
  27.  
  28.  
  29.  
  30. total = 0
  31. for node in range(nodes):
  32.     total += dfs(node, graph, salaries)
  33.  
  34. print(total)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement