Cycle in a directed graph DFS
unknown
java
3 months ago
1.8 kB
3
Indexable
import java.util.*; import java.util.concurrent.atomic.AtomicBoolean; class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); // Initialize adjacency list for (int i = 0; i < numCourses; i++) { adj.add(new ArrayList<>()); } // Build adjacency list (bi → ai) for (int i = 0; i < prerequisites.length; i++) { int ai = prerequisites[i][0]; int bi = prerequisites[i][1]; adj.get(bi).add(ai); } boolean[] visited = new boolean[numCourses]; boolean[] active = new boolean[numCourses]; AtomicBoolean cycle = new AtomicBoolean(false); // Run DFS on every unvisited node for (int i = 0; i < numCourses; i++) { if (!visited[i]) { dfs(i, visited, active, adj, cycle); if (cycle.get()) return false; // If cycle detected, return early } } return true; // If no cycle, all courses can be finished } public void dfs(int i, boolean[] visited, boolean[] active, List<List<Integer>> adj, AtomicBoolean cycle) { visited[i] = true; active[i] = true; for (int j = 0; j < adj.get(i).size(); j++) { int y = adj.get(i).get(j); if (!visited[y]) { dfs(y, visited, active, adj, cycle); } else if (active[y]) { // If y is in the active stack, we found a cycle cycle.set(true); return; // Return early as we don't need to continue DFS } } active[i] = false; // Remove from active recursion stack } }
Editor is loading...
Leave a Comment