题目链接：hdu1285

解题思路：裸拓扑排序 ，由于要输出字典序最小的ans，所以用堆作容器，复杂度由原来的O(V+E)变为O((V+E)*logV),题中输入的数据都符合DAG 的要求，所以不必判环。

解题细节

拓扑排序写法：

  • 初始化：将入度为0的节点V入队
  • 将入度为0的节点加入排序结果集中
  • 删除与入度为0的节点相连的边删除，相连的边入度-1
  • 将跟新边后入度为0的节点入队

AC代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>
using namespace std;

const int maxn = (int)5e2+5;

int book[maxn],n,m,u,v;
vector<int> vertex[maxn]; //邻接表
priority_queue<int, vector<int>, greater<int> > Q;

int main() {
	while (~scanf("%d%d", &n,&m)) {
		for (int i = 0; i <= n; i++) { //用0下标的向量保存拓扑排序序列
			vertex[i].clear();
		}
		memset(book,0,sizeof(book));
		for (int i = 0; i < m; i++) {
			scanf("%d%d",&u,&v);
			book[v]++; // 入度+1
			vertex[u].push_back(v); //加入邻接表中
		}
		
		while(!Q.empty()) {
			Q.pop();
		}
		for (int i = 1; i <= n; i++) {
			if(book[i] == 0) {
				Q.push(i);
			}
		}
		while(!Q.empty()) {
      u = Q.top();
      Q.pop();
      vertex[0].push_back(u);
      for (vector<int>::iterator it = vertex[u].begin(); it != vertex[u].end(); it++) {
				book[*it] --;
				if(book[*it] == 0) {
					Q.push(*it);
				}
			}
		}
		
		for (vector<int>::iterator it = vertex[0].begin(); it != vertex[0].end(); it++) {
			printf("%d%c",*it," \n"[it+1 == vertex[0].end()]);
		}
	}
	return 0;
}