Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/207.html

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Algorithm

Kahn’s Algorithms:

https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm

BFS based,

  • start from with vertices with 0 incoming edge,insert them into list S,at the same time we remove all their outgoing edges,
  • after that find new vertices with 0 incoming edges and go on.

Tarjan’s Algorithms:

https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm DFS based,

  • loop through each node of the graph in an arbitrary order,
  • initiating a depth-first search that terminates when it hits any node that has already been visited
  • since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node).

Code

  • 
    public class Course_Schedule {
    
        public class Solution_bfs {
            public boolean canFinish(int numCourses, int[][] prerequisites) { // Kahn's Algorithm
                if(numCourses <= 0) {
                    return false;
                }
    
                if(prerequisites == null || prerequisites.length == 0) {
                    return true;
                }
    
                int[] inDegree = new int[numCourses];
    
                // 1. setup indgree count
                for(int[] edge : prerequisites) {
                    inDegree[edge[0]]++;
                }
    
                Queue<Integer> queue = new LinkedList<>();
    
                // 2. start from node with no indgree, i.e. no prerquisites for this course
                for(int i = 0; i < inDegree.length; i++) {
                    if(inDegree[i] == 0) {
                        queue.offer(i);
                    }
                }
    
                List<Integer> result = new ArrayList<>();
    
                while(!queue.isEmpty()) {
                    int currentCourse = queue.poll();
                    result.add(currentCourse);
    
                    for(int[] edge : prerequisites) {
                        if(edge[1] == currentCourse) { // if a course requires current course
    
                            if(--inDegree[edge[0]] == 0) // -1, since current course is taken, and fulfill course edge[0]
                                queue.offer(edge[0]);
                        }
                    }
                }
    
                return result.size() == numCourses;
            }
        }
    
        public class Solution_dfs {
            public boolean canFinish(int numCourses, int[][] prerequisites) {
    
                if(prerequisites == null || prerequisites.length < 2) {
                    return true;
                }
    
                // 0 for not visited,1 for globally visited,-1 for visisted AND on current path
                int[] isVisited = new int[numCourses];
                List<List<Integer>> graph = new ArrayList<>();
    
                // 1. build graph
                for (int i = 0; i < numCourses; i++) {
                    graph.add(new ArrayList<>());
                }
                for (int[] each: prerequisites) {
                    graph.get(each[1]).add(each[0]);
                }
    
                // 2. dfs
                for (int i = 0; i < numCourses; i++) {
                    if (!dfs(i, isVisited, graph)) {
                        return false;
                    }
                }
    
                return true;
            }
    
            private boolean dfs(int courseIndex, int[] isVisited, List<List<Integer>> graph) {
                if (isVisited[courseIndex] == 1) {
                    return true;
                }
                if (isVisited[courseIndex] == -1) {
                    return false; // cycle found
                }
    
                isVisited[courseIndex] = -1;
                for (Integer next: graph.get(courseIndex)) {
                    if(!dfs(next, isVisited, graph)) {
                        return false;
                    }
                }
    
                isVisited[courseIndex] = 1;
                return true;
            }
        }
    
    }
    
    ############
    
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] g = new List[numCourses];
            Arrays.setAll(g, k -> new ArrayList<>());
            int[] indeg = new int[numCourses];
            for (var p : prerequisites) {
                int a = p[0], b = p[1];
                g[b].add(a);
                ++indeg[a];
            }
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = 0; i < numCourses; ++i) {
                if (indeg[i] == 0) {
                    q.offer(i);
                }
            }
            int cnt = 0;
            while (!q.isEmpty()) {
                int i = q.poll();
                ++cnt;
                for (int j : g[i]) {
                    if (--indeg[j] == 0) {
                        q.offer(j);
                    }
                }
            }
            return cnt == numCourses;
        }
    }
    
  • // OJ: https://leetcode.com/problems/course-schedule/
    // Time: O(V + E)
    // Space: O(V + E)
    class Solution {
    public:
        bool canFinish(int n, vector<vector<int>>& E) {
            vector<vector<int>> G(n);
            vector<int> indegree(n);
            for (auto &e : E) {
                G[e[1]].push_back(e[0]);
                ++indegree[e[0]];
            }
            queue<int> q;
            for (int i = 0; i < n; ++i) {
                if (indegree[i] == 0) q.push(i);
            }
            while (q.size()) {
                int u = q.front();
                q.pop();
                --n;
                for (int v : G[u]) {
                    if (--indegree[v] == 0) q.push(v);
                }
            }
            return n == 0;
        }
    };
    
  • '''
    >>> from collections import defaultdict
    
    >>> a = defaultdict(int)
    >>> a
    defaultdict(<type 'int'>, {})
    >>>
    >>> a['hehehe']
    0
    >>> a
    defaultdict(<type 'int'>, {'hehehe': 0})
    
    
    >>> a = defaultdict(list)
    >>> a
    defaultdict(<type 'list'>, {})
    >>> a['hehehe']
    []
    >>> a
    defaultdict(<type 'list'>, {'hehehe': []})
    '''
    class Solution:
        def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
            g = defaultdict(list)
            indeg = [0] * numCourses
            for a, b in prerequisites:
                g[b].append(a)
                indeg[a] += 1
            cnt = 0
            q = deque([i for i, v in enumerate(indeg) if v == 0])
            while q:
                i = q.popleft()
                cnt += 1
                for j in g[i]:
                    indeg[j] -= 1
                    if indeg[j] == 0:
                        q.append(j)
            return cnt == numCourses
    
    ############
    
    class Solution(object):
      def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
    
        def dfs(start, parent, visited, graph):
          visited[start] = 1
          for nbr in graph[start]:
            if visited[nbr] == 1:
              return False
            if dfs(nbr, start, visited, graph) == False:
              return False
          visited[start] = 2
          return True
    
        graph = [[] for _ in range(0, numCourses)]
        for pre in prerequisites:
          start, end = pre
          graph[start].append(end)
    
        visited = [0 for _ in range(0, numCourses)]
    
        for pre in prerequisites:
          start, end = pre
          if visited[start] == 0:
            if dfs(start, None, visited, graph) == False:
              return False
        return True
    
    
  • func canFinish(numCourses int, prerequisites [][]int) bool {
    	g := make([][]int, numCourses)
    	indeg := make([]int, numCourses)
    	for _, p := range prerequisites {
    		a, b := p[0], p[1]
    		g[b] = append(g[b], a)
    		indeg[a]++
    	}
    	q := []int{}
    	for i, v := range indeg {
    		if v == 0 {
    			q = append(q, i)
    		}
    	}
    	cnt := 0
    	for len(q) > 0 {
    		i := q[0]
    		q = q[1:]
    		cnt++
    		for _, j := range g[i] {
    			indeg[j]--
    			if indeg[j] == 0 {
    				q = append(q, j)
    			}
    		}
    	}
    	return cnt == numCourses
    }
    
  • function canFinish(numCourses: number, prerequisites: number[][]): boolean {
        let g = Array.from({ length: numCourses }, () => []);
        let indeg = new Array(numCourses).fill(0);
        for (let [a, b] of prerequisites) {
            g[b].push(a);
            ++indeg[a];
        }
        let q = [];
        for (let i = 0; i < numCourses; ++i) {
            if (!indeg[i]) {
                q.push(i);
            }
        }
        let cnt = 0;
        while (q.length) {
            const i = q.shift();
            ++cnt;
            for (let j of g[i]) {
                if (--indeg[j] == 0) {
                    q.push(j);
                }
            }
        }
        return cnt == numCourses;
    }
    
    
  • public class Solution {
        public bool CanFinish(int numCourses, int[][] prerequisites) {
            var g = new List<int>[numCourses];
            for (int i = 0; i < numCourses; ++i)
            {
                g[i] = new List<int>();
            }
            var indeg = new int[numCourses];
            foreach (var p in prerequisites)
            {
                int a = p[0], b = p[1];
                g[b].Add(a);
                ++indeg[a];
            }
            var q = new Queue<int>();
            for (int i = 0; i < numCourses; ++i)
            {
                if (indeg[i] == 0) q.Enqueue(i);
            }
            var cnt = 0;
            while (q.Count > 0)
            {
                int i = q.Dequeue();
                ++cnt;
                foreach (int j in g[i])
                {
                    if (--indeg[j] == 0) q.Enqueue(j);
                }
            }
            return cnt == numCourses;
        }
    }
    

All Problems

All Solutions