Cycle in a directed graph DFS

 avatar
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