任务调度

题目: 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

这道题是拓扑排序的应用。

http://baike.baidu.com/view/288212.htm

http://www.geeksforgeeks.org/topological-sorting/

拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

 1 typedef int JobID;
 2 
 3 /*
 4  * deps[id]表示任务id所依赖的任务
 5  * 如果存在合法的任务完成序列，返回true，否则返回false
 6  * 合法的任务序列请存放在参数result中（已经分配空间，不需要push_back）
 7  */
 8 bool jobSchedule(const map<JobID, vector<JobID> > &deps, int n,
 9                                    vector<JobID> &result) {
10     
11     vector<JobID> indegree(n+1, 0); // 计算图形入度
12     map<JobID, vector<JobID> > rmap;
13     map<JobID, vector<JobID> >::const_iterator it = deps.begin();
14     for(; it != deps.end(); it++) {
15         indegree[it->first] = it->second.size();
16         for(int i = 0; i < it->second.size(); i++) {
17             rmap[it->second[i]].push_back(it->first);
18         }
19     }
20     
21     stack<JobID> s;
22     for(int i = 1; i <= n; i++) {
23         if(indegree[i] == 0) {
24             s.push(i);
25         }
26     }
27     
28     for(int i = 0; i < n; i++) {
29         if(s.empty()) return false; // not finish schedule
30         JobID id = s.top(); 
31         s.pop();
32         result[i] = id;
33         for(int j = 0; j < rmap[id].size(); j++) {
34             indegree[rmap[id][j]]--;
35             if(indegree[rmap[id][j]] == 0) {
36                 s.push(rmap[id][j]);
37             }
38         }
39     }
40     return true;
41 }

解题思路：

1. 参考拓扑排序算法

2. stack为空(没有前驱的顶点不存在)时，图中仍然存在顶点，表示任务调度失败。