Easy BFS Topological sort, Java


  • 112
    J
    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;
    }

  • 3
    D

    wonderful. thanks.


  • 1
    W

    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.


  • 0
    J

    Yeah, I think it is O(V^2). Do you have any idea to make it better? Thanks!


  • 1
    W

    I used two maps Map<Integer, Set<Integer>> to store the graph. There fore I will only use containsKey() or contains() to check if matrix[course][i] is 0 or not. But I'm not sure if it is O(V+E).


  • 13
    J

    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;

  • 0
    T

    Is this solution memory-efficient? The matrix seems to be a big overhead.
    Can you please provide suggestions to my answer as well:
    https://leetcode.com/discuss/60669/logical-and-easy-to-understand-how-to-improve


  • 0
    M

    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;
    
    }

  • 0

    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 the if (matrix[pre][ready] == 0) check. :P


  • 0
    J

    I like this one, easy to understand. Thanks for sharing!


  • 19
    E

    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;
    }
    

    }


  • 0

    Good solution ! If there is some case like [1,0] [0,1], then the integer count > numCourses ! Thanks


  • 0
    W
    This post is deleted!

  • 0
    G

    simple and clear.


  • 0
    B

    Got memory exceeded?


  • 5
    S

    It would be more understandable if pair[0]++, not pair[1]++ is used for counting in-degrees, because [0, 1] means 1 -> 0. The result is the same.


  • 0
    K

    Just by replacing queue.offer to queue.add it gives MLE ,confused ???


  • 0
    D

    Beautiful code I like it indeed


  • 0
    O
    This post is deleted!

  • 1

    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
    

Log in to reply
 

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