public boolean canFinish(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses]; // i > j
int[] indegree = new int[numCourses];
for (int i=0; i<prerequisites.length; i++) {
int ready = prerequisites[i][0];
int pre = prerequisites[i][1];
if (matrix[pre][ready] == 0)
indegree[ready]++; //duplicate case
matrix[pre][ready] = 1;
}
int count = 0;
Queue<Integer> queue = new LinkedList();
for (int i=0; i<indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int i=0; i<numCourses; i++) {
if (matrix[course][i] != 0) {
if (indegree[i] == 0)
queue.offer(i);
}
}
}
return count == numCourses;
}
Easy BFS Topological sort, Java


Could you provide the Time complexity for your solution using adjacent matrix?`
while (!queue.isEmpty()) { int course = queue.poll(); count++; for (int i=0; i<numCourses; i++) { if (matrix[course][i] != 0) { if (indegree[i] == 0) queue.offer(i); } } }
For this part, I kind of guess it is not O(V^2) instead of O(V+E) because you always scan from i=0 to numCourses to check whether the matrix[course][i] is 0 or not.

I rewrote the code, I think that would be O(V + E)
// O(V + E) List<Integer>[] matrix = new List[numCourses]; int[] indegree = new int[numCourses]; // E part for (int[] pre : prerequisites) { int preCourse = pre[1]; int readyCourse = pre[0]; List<Integer> list = matrix[preCourse]; if (list == null) { list = new LinkedList<>(); matrix[preCourse] = list; } list.add(readyCourse); indegree[readyCourse]++; } Queue<Integer> queue = new LinkedList<>(); for (int i=0; i<numCourses; i++) { if (indegree[i] == 0) queue.offer(i); } int count = 0; // V part while (!queue.isEmpty()) { int vertex = queue.poll(); count++; List<Integer> adjacent = matrix[vertex]; if (adjacent == null) continue; for (int neighbor : adjacent) { indegree[neighbor]; if (indegree[neighbor] == 0) queue.offer(neighbor); } } return count == numCourses;

Is this solution memoryefficient? The matrix seems to be a big overhead.
Can you please provide suggestions to my answer as well:
https://leetcode.com/discuss/60669/logicalandeasytounderstandhowtoimprove

This is my code, very similar idea. But why got TLE.....
public boolean canFinish(int numCourses, int[][] prerequisites) { HashMap<Integer, Set<Integer>> cantake = new HashMap<Integer, Set<Integer>>(); HashSet<Integer> remain = new HashSet<Integer>(); HashSet<Integer> finished = new HashSet<Integer>(); for (int i = 0; i < prerequisites.length; ++i) { remain.add(prerequisites[i][0]); if (cantake.containsKey(prerequisites[i][1])) { cantake.get(prerequisites[i][1]).add(prerequisites[i][0]); } else { Set<Integer> list = new HashSet<Integer>(); list.add(prerequisites[i][0]); cantake.put(prerequisites[i][1], list); } } for (int i = 0; i < numCourses; ++i) if (!remain.contains(i)) finished.add(i); for (int i = 0; i < numCourses; i++) { int size = finished.size(); for (int taking : cantake.keySet()) { if (finished.contains(taking)) { finished.addAll(cantake.get(taking)); } } // If unchanged, break; if (size == finished.size()) break; } return finished.size() == numCourses; }

Your code below using
LinkedList
to represent the graph handles the case where multiple edges exist between two node perfectly. And I'd like to mention that, in your above code it's easy to assign weight to the edges to represent the duplicate edges so that you avoid theif (matrix[pre][ready] == 0)
check. :P

I got this.
public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int[] indegree = new int[numCourses]; Queue<Integer> queue = new LinkedList<Integer>(); for(int[] pair:prerequisites){ indegree[pair[1]]++; } for(int i=0;i<indegree.length;i++){ if(indegree[i]==0){ queue.add(i); } } int select = 0; while(!queue.isEmpty()){ numCourses; int course = queue.poll(); for(int[] pair:prerequisites){ if(pair[0]==course){ indegree[pair[1]]; if(indegree[pair[1]]==0){ queue.add(pair[1]); } } } } return numCourses==0; }
}

Beautiful. Thanks for sharing.
Below is a Python translation for anyone interested:
def canFinish(self, numCourses, prerequisites): matrix = [[] for _ in range(numCourses)] indegree = [0] * numCourses for dep in prerequisites: cur, pre = dep matrix[pre].append(cur) indegree[cur] += 1 q = collections.deque() for i in range(numCourses): if indegree[i] == 0: q.append(i) count = 0 while q: cur = q.popleft() count += 1 neighbors = matrix[cur] for n in neighbors: indegree[n] = 1 if indegree[n] == 0: q.append(n) return count == numCourses