欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑排序

程序员文章站 2022-03-14 19:51:56
...
 							 任务拓扑排序 
一个工程被分解成n个子任务,编号为0至n-1。要完成整个工程需要完成所有的子任务。其中一些子任务必须先于另外一些子任务被完成。给定各子任务之间的先后关系,请编写程序给出一个合理的任务完成顺序,若工程不可行,程序亦能识别。

输入格式:
输入第一行为两个整数n和e,均不超过100。n表示子任务数。接下来e行,表示已知的两个子任务间的先后关系,每行为两个整数a和b,表示任务a必须先于任务b完成。

输出格式:
若工程不可行(一些子任务以自己为先决条件),输出“unworkable project”;若工程可行,输出为1行整数,每个整数后一个空格,为n个子任务的编号,表示子任务的完成顺序,如果有多种可能的顺序,则输出字典序最小者。

注:字典序,即对象在字典中的顺序。对于两个数字序列,从第一个数字开始比较,当某一个位置的数字不同时,该位置数字较小的序列,字典序较小,例如1 2 3 91 2 4 5小,1 2 8 91 2 10 3小。

输入样例1:
3 2
0 1
1 2
输出样例1:
0 1 2 
输入样例2:
3 3
0 1
1 2
2 0
输出样例2:
unworkable project

本题链接:
https://pintia.cn/problem-sets/1381240908960317440/problems/1381542114953871360

这道题考察拓扑排序。也是我第一次写拓扑排序:
感觉挺简单的,写了我的版本以及套板子写的一个版本。
套板子的版本:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue> 
int mapp[101][101];
int du[101];//初始值为0? 
int n,e,cnt; 
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;//
vector<int>g[101];
int tpsort()//关键! 
{
	int num=0;
	for(int i=0;i<n;i++)//现先将所有度为0的点入队 
	{
		if(du[i]==0)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int u=q.top();
		cout<<u<<" ";
		q.pop();
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			du[v]--;
			if(du[v]==0)
				q.push(v);
		}
		g[u].clear();
		num++;
	 } 
	
	if(num!=n)
	cout<<"unworkable project";
}
int main()
{
	cin>>n>>e;
	for(int i=0;i<e;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		du[b]++;
	}
	tpsort();
}

下面一个是我自己写的版本:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue> 
int mapp[101][101];
int du[101];//初始值为0? 
int n,e,cnt;
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
vector<string>v;
int tpsort()//关键! 
{
	int num=0;
	for(int i=0;i<n;i++)
	{
		if(du[i]==0)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int u=q.top();
		cout<<u<<" ";
		q.pop();
		for(int i=0;i<n;i++)
		{
			if(mapp[u][i]==1)
			{
				du[i]--;
				if(du[i]==0)
					q.push(i);
			}
			
		} 
	}
}
int main()
{
	cin>>n>>e;
	for(int i=0;i<e;i++)
	{
		int a,b;
		cin>>a>>b;
		mapp[a][b]=1;
		du[b]++;
	}
	tpsort();
}

写法实现是挺容易的,大家也可以试试。