1940_Ordering_Tasks

题目链接：

http://soj.me/1940

题目大意：

输入n和m，n代表任务的个数，m代表任务间先后关系的个数．后面输入m个先后关系，比如1 4表示任务1要在任务4之前完成．找到一种完成所有任务的顺序，满足所有要求的先后顺序，有多个解时要求输出字典序最小的．

思路：

拓扑排序问题，但是要求输出字典序最小的.输入实际上是一个有向图，建立一个数组inDegree记录每个任务之前要完成的任务，用vector数组记录每个任务指向的任务．开一个最小优先队列readyTasks，这样可以保证队列里面永远是从小到大的顺序．一开始先将inDegree的点即根结点放进队列中，然后逐个访问队列头的结点，对于每个队列头的结点，将它放到结果队列的尾部，并将指向的结点的inDegree--，如果该子结点入度等于０了就可以将它放到readyTasks中

代码：

#include <iostream>#include <vector>#include <queue>#include <memory.h>using namespace std;int main() {	int numTestcases;	cin >> numTestcases;	while(numTestcases--){		int n, m;		cin >> n >> m;		int inDegree[n + 1];		int result[n];		vector<int> tasks[n + 1];		memset(inDegree, 0, sizeof(inDegree));		for (int i = 0; i < m; ++i) {			int a, b;			cin >> a >> b;			inDegree[b]++;			tasks[a].push_back(b);		}		priority_queue<int, vector<int>, greater<int> > readyTasks;//使用最小优先队列可以自动按照从小到大排序		for (int i = 1; i <= n; ++i) {//先将所有根结点放进队列中待选			if(inDegree[i] == 0)				readyTasks.push(i);		}		int numFinished = 0;		while(!readyTasks.empty()){			int cur = readyTasks.top();			result[numFinished++] = cur;			readyTasks.pop();			vector<int> ::iterator it;			for(it = tasks[cur].begin(); it != tasks[cur].end();it++){				int temp = *it;				inDegree[temp]--;				if(inDegree[temp] == 0)//当前趋结点全部完成时可以开始这个任务					readyTasks.push(temp);			}		}		for (int i = 0; i < n; ++i) {			cout  << result[i] << " ";		}		cout << endl;	}	return 0;}

Sicily 1940. Ordering Tasks 解题报告