Pass all cases except the last one. Do u guys have any idea? Thanks.


  • 0
    B

    Basically I used BFS to explore level by level. When visiting each node in level d, check that whether it has been visited in the previous levels, if so return false. After visiting all nodes in level d, we put them in the explored set. The code below passed all 31/32 cases, and failed the last case with 700 courses. The expected result is false. Could you help me find out the bugs? Thank you!

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List[] map = new List[numCourses];
    
        for (int i = 0; i < numCourses; i++) {
            map[i] = new ArrayList<>();
        }
        for (int[] pair : prerequisites) {
            map[pair[0]].add(pair[1]);
        }
    
        Queue<Integer> frontier = new LinkedList<>();
        frontier.add(0);
        frontier.add(null);
        Set<Integer> explored = new HashSet<>();
        Set<Integer> level = new HashSet<>();
    
        while (frontier.size() > 1) {
            Integer course = frontier.remove();
            Integer next = frontier.element();
            if (course != null) {
                if (explored.contains(course)) {
                    return false;
                }
                level.add(course);
                frontier.addAll(map[course]);
                if (next == null) {
                    explored.addAll(level);
                    level.clear();
                    frontier.add(null);    
                }                
            }
        }
        return true;
    }

Log in to reply
 

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