Level 1 Inherited permissions
There are n roles, numbered 0..n-1. perms[i] is a list of the permission names that role i holds itself. inherits is a list of [parent, child] pairs: the child gets everything the parent has, including everything the parent inherited. The pairs form a DAG (no cycles), and a role can have several parents.
Write effective_permissions(perms: list[list[str]], inherits: list[list[int]]) -> list[list[str]]. It returns, for each role, the sorted list (without duplicates) of permissions it has once inheritance is applied.
Graphs have up to 50,000 roles and 150,000 edges.
⭐ Bonus: a speed test with a 50,000-role chain earns a star if each edge is handled once, without recursion. Walking up through every role's ancestors separately is too slow for it.
effective_permissions([["read"], ["write"], ["admin"], []],
[[0, 1], [1, 2], [0, 3]])
# [["read"], ["read", "write"], ["admin", "read", "write"], ["read"]]
Show hint
A role's answer is its own permissions plus its parents' finished answers, so handle each role only after all of its parents are done.