https://leetcode.com/problems/course-schedule/description/
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?
Example 1:
Input: 2, [[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: 2, [[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.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites
就像大學修課一樣，每堂課都會有先修課程，因為你不先修A課程，B課程你可能聽不懂。
開學前系上的教授們會聚在一起研究課程的先後關係，然後公布出來。
本題input一堆pair(a,b)，表示a是b的先修課程，當然b的先修課程可能不只一個，a本身也可能有其他先修課程。請回傳這個課程設計是否可行。
[Solution]
Check if there is a loop in the directed graph.
To solve this problem, you have to
1.Be able to transform the input into a directed graph.
2.Understand that the courses can be finish as long as there is no cycle in the directed graph.
3.Know who to detect cycle in the directed graph.
Let's go through it one by one.
1.Be able to transform the input into a directed graph.
The input data is only description of edges. We have to transform it into "adjacency list" which is a popular data structure used to describe Graph.
2.Understand that the courses can be finish as long as there is no cycle in the directed graph.
If there is a cycle in the directed graph, you can never finish the course.
For example, if there exist a cycle A-->??-->X, X-->??-->A
That means to before starting X, you must finish A. Before starting A, you must finish X.
This is obviously impossible.
If there is no cycle, you can finish all courses by keep eliminate those courses who have no prerequisites, or courses who's prerequisites are all been eliminated.
3.Know who to detect cycle in the directed graph.
We eliminate those courses who have no prerequisite, and update the graph. And so on..., until we can do it no more. Finally we check if there is any course left behind.
e.g.
Originally A-->B-->C,
We eliminate A who have no prerequisite. Then the graph become, B-->C.
We eliminate B who have no prerequisite. Then the graph become, C.
We eliminate C who have no prerequisite.
Then we can do it no more, because there is no more courses.
So this courses design is possible to be finished.
Originally A-->B-->C-->B, (C have a prerequisite B).
We eliminate A who have no prerequisite. Then the graph become, B-->C-->B.
Then can do it no more, because the C and B all have prerequisite.
So this courses design is impossible to be finished.
Because C and B is left behind, and there is no way to finish them since they have prerequisite.
Ok, let's write codes.
bool canFinish(int n, vector<pair<int, int>>& edge) {
//idea: node i's indegree = 0 ,node is ready
//idea: after node i executed, if(edge(i,k) exist) the node k's indegree--
queue<int> q;
int executed=0;//how many node are executed (push to queue)
vector<int> indegree(n,0);//indegree of node 0~n-1
unordered_map<int,vector<int>> adjlist;//<name of node, edge start from this node>
for(auto it : edge){
indegree[it.second]++;//build init indegree
adjlist[it.first].push_back(it.second);
}
for(int it=0;it<n;it++)
if(indegree[it]==0) q.push(it);
while(!q.empty()){
int cur = q.front(); q.pop(); executed++;
for(auto it : adjlist[cur]){
if(--indegree[it]==0)
q.push(it);
}
}
return (executed == n);
}
