拓扑排序的思路,

输出格式:在出队列q的时候稍微改一下,因为对输出格式有要求,出队时输出,同时计数number,如果number=0说明到最后一个了,此时不输出空格

符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前:把队列换成优先队列,且是小顶堆,这时候要注意头文件的添加include<functional>,没加在oj提交的时候一直报编译错误

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<functional>   //使用priority_queue<int,vector<int>,greater<int>> q时添加,要不然会报编译错误 
using namespace std;

const int MAXN=501;
vector<int> graph[MAXN];
int inDegree[MAXN];

queue<int> res;
bool TopologicalSort(int n) {
	priority_queue<int,vector<int>,greater<int>> q;
	int number=0;
	for(int i=1; i<=n; i++) {
		if(inDegree[i]==0) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u=q.top();
		printf("%d",u);
		q.pop();
		number++;
		if(n!=number){
			printf(" ");
		} 
		for(int i=0; i<graph[u].size(); i++) {
			int v=graph[u][i];
			inDegree[v]--;
			if(inDegree[v]==0) {
				q.push(v);
			}
		}
	}
	return n==number;
}

int main() {
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF) {
		memset(graph,0,sizeof(graph));
		memset(inDegree,0,sizeof(inDegree));
		while(m--) {
			int x, y;
			scanf("%d%d",&x,&y);
			graph[x].push_back(y);
			inDegree[y]++;
		}
		TopologicalSort(n);
		printf("\n");
	}
	return 0;
}

 

Logo

华为开发者空间,是为全球开发者打造的专属开发空间,汇聚了华为优质开发资源及工具,致力于让每一位开发者拥有一台云主机,基于华为根生态开发、创新。

更多推荐