toposort
say toposort if a function [sorted nodes] = f(G) s.t. the local pair based constraints are turned into a GLOBAL linear order ( one of )
toposort(G) = one valid linearization of the partial order encoded by G
aka it’s partial to global ordering
it’s called kahn’s algo but I always forget the name and “indegree method” is more memorable
indeg(i) -> indegree of node i in graph
zeros -> set of nodes with zero indeg
while zeros:
u := pop zeros
add u to ans
indeg[neigh(u)...] -= 1 THEN update zeros
if len(ans) < len(nodes):
NO ORDER
the main usgae of toposort is graph decomposition to a DAG as then you can model it as a dp ( dp is basically a dag of transitions )
problems
- alien dictionary: given list of words, find if there is some possible order on characters
- edge case: longer word before smaller ( prefix match ) = no order
- multiple toposorts
- sort items by groups repsecting dependencies
- build a matrix with conditions