博客

#Ordering Tasks

##工具

• queue
• vector

##思路

主要是处理好每个点的入度的关系，当一个节点的前驱节点全部被处理的时候，表示该节点能被处理，每处理一个节点，他对应的后序节点的入度都减1

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <memory.h>
using namespace std;

int main() {
	int case1, point, num_edge;
	cin >> case1;
	while(case1--) {
		cin >> point >> num_edge;
		int a, b;
		vector<int> result;
		priority_queue<int, vector<int>, greater<int> > readyTasks;
		vector<int> task[point+1];
		int indegree[point+1];
		memset(indegree,0,sizeof(indegree));
		for(int i = 0; i < num_edge; i++) {
			cin >> a >> b;
			indegree[b]++;
			task[a].push_back(b);
		}

		for(int i = 1; i <= point; i++) {
			if(indegree[i] == 0) {
				readyTasks.push(i);
			}
		}

		while(!readyTasks.empty()) {
			int temp = readyTasks.top();
			readyTasks.pop();
			result.push_back(temp);
			for(auto it = task[temp].begin(); it != task[temp].end(); it++) {
				indegree[*it]--;
				if(indegree[*it] == 0) {
					readyTasks.push(*it);
				}
			}
		}
		for(int i = 0; i < result.size(); i++) {
			cout << result[i] << " ";
		}
		cout << endl;
	}
	return 0;
}

更多技术博客

：

https://vilin.club/