Demo entry 6352927

c++

   

Submitted by anonymous on Mar 28, 2017 at 09:06
Language: C++. Code size: 1.1 kB.

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define M 505
using namespace std;
vector<int> map[M];		//vector动态数组 
int topNum[M],ans[M];
int n,m;

void TopSort(){
	priority_queue<int,vector<int>,greater<int> >q;
	for(int i=1;i<=n;i++){
		if(map[i][0] == 0){
			q.push(i);		//无入度的加入队列 
		}
	}	
	int cnt = 0;
	while(!q.empty()){
		int u = q.top();	
		q.pop();
		topNum[u] = ++cnt;	//记录名次 
		for(int i=1;i<map[u].size();i++){
			int son = map[u][i];	//找该无入度节点的儿子节点 
			if(--map[son][0] == 0){
				q.push(son);	//无入度的加入队列 
			}
		}
	}
	if(cnt != n){	//图中存在环, 无拓扑序 
		return;
	}
	for(int i=1;i<=n;i++){
		ans[topNum[i]] = i;
	}	
	for(int i=1;i<=n;i++){
		printf("%d%c",ans[i],i==n?'\n':' ');
	}
}

int main(){
	while(~scanf("%d %d",&n,&m)){
		for(int i=1;i<=n;i++){
			map[i].clear();
			map[i].push_back(0);
		}
		for(int i=1;i<=m;i++){
			int s,e;
			scanf("%d %d",&s,&e);
			map[s].push_back(e);	//map[s]开辟出map[s][e] 
			++map[e][0];	
			/*
				拓扑排序从1开始,我们可以用0下标来记录
				该节点入度的数量 
			*/	
		}
		TopSort();
	}
	return 0;
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).