There are a total of n courses you have to take, labeled from
0
to n - 1
.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
[0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
Hints:
The problem is equivalent to finding if a directed graph contains a circle. Thus we could use a DFS or BFS solution.
DFS Solution:
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited.
visited = -1, means this node has been visited.
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.
Code (Java):
Update on 4/22/19: Using topological sorting
- This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.
The problem is equivalent to finding if a directed graph contains a circle. Thus we could use a DFS or BFS solution.
DFS Solution:
Use an array to mark if the node has been visited before. Here is a small trick to save some time. Instead of using a boolean array, we use an integer array int[] visited.
visited = -1, means this node has been visited.
visited = 1, means this node has been validated which does not include a circle. Thus if we saw that a node has been validated, we don't need to calculate again to find out the circle starting from this node. e.g. [0, 1] [1, 2] [2, 3] [3, 4]. For the node 0, we have already validated 2 3 and 4 do not have a circle. Thus we don't need to calculate for the node 2 3 4 again.
Code (Java):
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 | public class Solution { public boolean canFinish( int numCourses, int [][] prerequisites) { if (numCourses <= 0 ) { return true ; } if (prerequisites == null || prerequisites.length == 0 ) { return true ; } // First transform the edge list to adj. list Map<Integer, List<Integer>> adjList = new HashMap<>(); for ( int [] edge : prerequisites) { if (adjList.containsKey(edge[ 0 ])) { List<Integer> neighbors = adjList.get(edge[ 0 ]); neighbors.add(edge[ 1 ]); adjList.put(edge[ 0 ], neighbors); } else { List<Integer> neighbors = new ArrayList<Integer>(); neighbors.add(edge[ 1 ]); adjList.put(edge[ 0 ], neighbors); } } int [] visited = new int [numCourses]; // Check if the graph contains a circle, if yes, return false. for ( int i = 0 ; i < numCourses; i++) { if (hasCircles(i, visited, adjList)) { return false ; } } return true ; } private boolean hasCircles( int vertexId, int [] visited, Map<Integer, List<Integer>> adjList) { if (visited[vertexId] == - 1 ) { return true ; } if (visited[vertexId] == 1 ) { return false ; } visited[vertexId] = - 1 ; List<Integer> neighbors = adjList.get(vertexId); if (neighbors != null ) { for ( int neighbor : neighbors) { if (hasCircles(neighbor, visited, adjList)) { return true ; } } } visited[vertexId] = 1 ; return false ; } } |
Update on 4/22/19: Using topological sorting
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 | public class Solution { /* * @param numCourses: a total of n courses * @param prerequisites: a list of prerequisite pairs * @return: true if can finish all courses or false */ public boolean canFinish( int numCourses, int [][] prerequisites) { // write your code here if (numCourses <= 0 || prerequisites == null || prerequisites.length == 0 ) { return true ; } // step 1: create adjlist and in-=degree map // Map<Integer, Integer> nodeToIndegreeMap = new HashMap<>(); Map<Integer, List<Integer>> adjList = new HashMap<>(); for ( int i = 0 ; i < numCourses; i++) { nodeToIndegreeMap.put(i, 0 ); adjList.put(i, new ArrayList<>()); } for ( int [] prerequisite : prerequisites) { int inDegree = nodeToIndegreeMap.get(prerequisite[ 1 ]); inDegree += 1 ; nodeToIndegreeMap.put(prerequisite[ 1 ], inDegree); } for ( int [] prerequisite : prerequisites) { List<Integer> neighbors = adjList.get(prerequisite[ 0 ]); neighbors.add(prerequisite[ 1 ]); adjList.put(prerequisite[ 0 ], neighbors); } // step 2: get all nodes with indegree 0 and put into the queuue // Queue<Integer> queue = new LinkedList<>(); int numNodes = 0 ; for (Integer key : nodeToIndegreeMap.keySet()) { int indegree = nodeToIndegreeMap.get(key); if (indegree == 0 ) { queue.offer(key); numNodes += 1 ; } } while (!queue.isEmpty()) { int curNode = queue.poll(); for ( int neighbor : adjList.get(curNode)) { int indegree = nodeToIndegreeMap.get(neighbor); indegree -= 1 ; nodeToIndegreeMap.put(neighbor, indegree); if (indegree == 0 ) { queue.offer(neighbor); numNodes += 1 ; } } } return numNodes == numCourses; } } |
No comments:
Post a Comment