Topological Sort (Kahn's)

1import java.util.*;
2 
3public class Main {
4    public static List<String> topologicalSort(Map<String, List<String>> graph) {
5        Map<String, Integer> inDegree = new HashMap<>();
6        graph.keySet().forEach(node -> inDegree.put(node, 0));
7        graph.values().forEach(edges -> edges.forEach(node -> inDegree.merge(node, 1, Integer::sum)));
8        Queue<String> queue = new ArrayDeque<>();
9        inDegree.forEach((node, degree) -> { if (degree == 0) queue.add(node); });
10        List<String> order = new ArrayList<>();
11        while (!queue.isEmpty()) {
12            String node = queue.remove();
13            order.add(node);
14            for (String next : graph.getOrDefault(node, List.of())) {
15                if (inDegree.merge(next, -1, Integer::sum) == 0) queue.add(next);
16            }
17        }
18        if (order.size() != inDegree.size()) throw new IllegalArgumentException("Graph contains a cycle");
19        return order;
20    }
21 
22}