Task Schedule

来源：itint5

原帖：http://www.itint5.com/oj/#10

题目：
有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。
样例：
n=5
1->2,3
3->4
上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5
Solution: topological sorting
Refer to http://www.geeksforgeeks.org/topological-sorting/

代码：

 /*  
  * deps[id]表示任务id所依赖的任务  
  * 如果存在合法的任务完成序列，返回true，否则返回false  
  * 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）  
    2->1; 3->1  
    4->3  
    拓扑排序方法如下:  
    (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.  
    (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.  
    (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.  
  */  
   
 typedef int JobID;  
 // BFS  
 // deps: <key, node(-->key) INDEGREE>  
 // rmap: <key, node(<--key) OUTDEGREE>  
 bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n, vector<JobID> &result) {  
   vector<JobID> indegree(n+1, 0); // 计算图形入度  
   map<JobID, vector<JobID>> rmap; //   
   for (auto it = deps.begin(); it != deps.end(); it++) {  
     indegree[it->first] = it->second.size();  
     for (int i = 0; i < it->second.size(); i++) {  
       rmap[it->second[i]].push_back(it->first);  
     }  
   }  
   stack<JobID> s;  
   for (int i = 1; i <= n; i++) {  
     if(indegree[i] == 0) {  
       s.push(i);  
     }  
   }  
   for (int i = 0; i < n; i++) {  
     if (s.empty()) return false;  
     JobID id = s.top(); s.pop();  
     result[i] = id;  
     for (int j = 0; j < rmap[id].size(); j++) {  
       indegree[rmap[id][j]]--;  
       if(indegree[rmap[id][j]] == 0) {  
         s.push(rmap[id][j]);  
       }  
     }  
   }  
   return true;  
 }