[Java/DFS] Code that works but not understandable is not a good code


  • 0
    J
    public class Solution {
    private static final int UNVISITED = 0;
    private static final int VISITING = 1;
    private static final int VISITED = 2;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1) return true;
        int N = numCourses;
        
        HashMap<Integer, List<Integer>> edges = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < prerequisites.length; i++) {
            int src = prerequisites[i][0];
            int dest = prerequisites[i][1];
            if (edges.containsKey(src)) {
                edges.get(src).add(dest);
            } else {
                List<Integer> l = new ArrayList<Integer>();
                l.add(dest);
                edges.put(src, l);
            }
        }
        
        int[] status = new int[N];
        for (int i = 0; i < numCourses; i++) {
            if (status[i] == UNVISITED) {
                if (!isAcyclic(i, edges, status)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isAcyclic(int num, HashMap<Integer, List<Integer>> edges, int[] status) {
        if (status[num] == VISITED)
            return true;
        if (status[num] == VISITING)
            return false;
        status[num] = VISITING;
        if (edges.containsKey(num)) {
            List<Integer> neighbors = edges.get(num);
            for (int v:neighbors) {
                if (!isAcyclic(v, edges, status)) return false;
            }
        }
        status[num] = VISITED;
        
        return true;
    }
    

    }


Log in to reply
 

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