Getting dressed: socks before shoes, shirt before tie. You can only put something on once everything it depends on is already on.
Clues that point here
→ Prerequisites or dependencies
→ "Is it possible to finish all courses?"
→ Build order, task scheduling
→ Directed acyclic graph
Not this pattern when
✕ The graph is undirected
✕ There are cycles you must handle differently
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Topological Sort · template
int[] indegree = new int[n];
for (int[] e : edges) indegree[e[1]]++;
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) q.offer(i);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int node = q.poll();
order.add(node);
for (int next : graph.get(node)) if (--indegree[next] == 0) q.offer(next);
}
return order.size() == n ? order : List.of(); // smaller means a cycle