leetcode-submissions/graph/0207-course-schedule/solution.java at main · SpookyJumpyBeans/leetcode-submissions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 207. Course Schedule
// https://leetcode.com/problems/course-schedule/
// Medium | Java | Accepted 2026-08-12
// Runtime 10 ms | Memory 46.9 MB

/*
Method using cycle detection and DFS

class Solution {
    boolean[] visited;
     Map<Integer, List<Integer>> map = new HashMap<>();
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for(int i = 0; i<prerequisites.length; i++)
        {
               int course = prerequisites[i][0];
               int prereq = prerequisites[i][1];
               if(!map.containsKey(course))
               {
                map.put(course, new ArrayList<>());
               }
               map.get(course).add(prereq);
        }
        visited = new boolean[numCourses];

        for(int j = 0; j<numCourses; j++)
        {
            boolean flag = recurse(new boolean[numCourses], j);
            if(!flag)
            {
                return false;
            }
        }
        return true;
    }

    public boolean recurse(boolean[] currPath, int node)
    {
        if(map.containsKey(node))
        {
        visited[node] = true;
        currPath[node] = true;
        for(int neighbor : map.get(node))
        {
            if(!visited[neighbor])
            {
                if(!recurse(currPath, neighbor))
                {
                    return false;
                }
            }
            if(currPath[neighbor])
            {
                return false;
            }
        }
        currPath[node] = false;
        }
        return true;
    }
}
*/

class Solution {
     Map<Integer, List<Integer>> map = new HashMap<>();
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] counts = new int[numCourses];
        for(int[] i : prerequisites)
        {
            map.computeIfAbsent(i[0], k -> new ArrayList<>()).add(i[1]);
            counts[i[1]]++;
        }
        Queue<Integer> bfs = new LinkedList<>();
        for(int j = 0; j<numCourses; j++)
        {
            if(counts[j]==0)
            {
                bfs.add(j);
            }
        }
        int count = 0;
        while(!bfs.isEmpty())
        {
            int front = bfs.poll();
            List<Integer> neighbors = map.get(front);
            count++;
            if(neighbors!=null)
            {
            for(int k = 0; k<neighbors.size(); k++)
            {
                counts[neighbors.get(k)]--;
                if(counts[neighbors.get(k)]==0)
                {
                    bfs.add(neighbors.get(k));
                }
            }
            }
        }
        return count == numCourses ? true : false;
    }
}