Java DFS to check acyclic


  • 0
    G

    Simply do as <CLRS> told as: using white, gray, and black to label node's status.

    public class Solution {
        private static int WHITE = 0;
        private static int GRAY = 1;
        private static int BLACK = 2;
        
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Set<Integer>[] g = (Set<Integer>[]) new Set[numCourses];
            for (int[] edge : prerequisites) {
                int end = edge[0];
                int tail = edge[1];
                if (g[tail] == null) {
                    g[tail] = new HashSet<>();
                }
                g[tail].add(end);
            }
            int[] visited = new int[numCourses];
            Arrays.fill(visited, WHITE);
            for (int v = 0; v < numCourses; v++) {
                if (visited[v] == WHITE &&
                    !dfs(g, v, visited)) {
                    return false;
                }
            }
            
            return true;
        }
        
        private boolean dfs(Set<Integer>[] g, int v, int[] visited) {
            visited[v] = GRAY;
            if (g[v] != null) {
                for (int end : g[v]) {
                    if (visited[end] == GRAY ||
                        (visited[end] == WHITE && !dfs(g, end, visited))) {
                        return false;
                    }
                }
            }
            visited[v] = BLACK;
            return true;
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.