Unexpected Results from Topological Sort Implementation in Java - Cycle Detection Failing
I'm updating my dependencies and I need help solving I'm maintaining legacy code that Quick question that's been bugging me - I'm currently working on a topological sort implementation in Java using Kahn's algorithm, but I'm facing issues with cycle detection in my directed graph. The algorithm should return an empty list if a cycle is detected, but it seems to be outputting a valid topological order even when there is a cycle in the graph. Here's the relevant portion of my code: ```java import java.util.*; public class TopologicalSort { public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) { List<Integer> order = new ArrayList<>(); int[] inDegree = new int[numCourses]; Map<Integer, List<Integer>> graph = new HashMap<>(); for (int[] p : prerequisites) { graph.putIfAbsent(p[1], new ArrayList<>()); graph.get(p[1]).add(p[0]); inDegree[p[0]]++; } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { queue.offer(i); } } while (!queue.isEmpty()) { int current = queue.poll(); order.add(current); if (graph.containsKey(current)) { for (int neighbor : graph.get(current)) { inDegree[neighbor]--; if (inDegree[neighbor] == 0) { queue.offer(neighbor); } } } } return order.size() == numCourses ? order : new ArrayList<>(); } } ``` I've tested it with a few graphs, including one with a cycle: ```java int[][] prerequisites = { {1, 0}, {0, 1} }; // This should detect a cycle TopologicalSort ts = new TopologicalSort(); System.out.println(ts.topologicalSort(2, prerequisites)); // Expected an empty list ``` However, the output is `[0, 1]`, which is incorrect since there is a cycle. I've double-checked the in-degree calculations and the graph construction, and they seem fine. Is there something I'm missing here regarding cycle detection? How should I modify my implementation to correctly handle this case? Any insights would be greatly appreciated! Is there a better approach? Any pointers in the right direction? My team is using Java for this desktop app.