UVA 10305 Ordering Tasks(拓扑排序的队列解法)

题目链接:

https://vjudge.net/problem/UVA-10305#author=goodlife2017

题目描述

John有n个任务,但是有些任务需要在做完另外一些任务后才能做。

输入

输入有多组数据,每组数据第一行有两个整数1 <= n <= 100mn是任务个数(标记为1n),m两个任务直接关系的数量。在此之后,有m行,每行有2个整数ij,代表任务i必须在任务j之前完成。用n = m = 0结束整个输入。

输出

每一个数据对应一行n个整数,代表任务完成的顺序。

样例输入

	5 4
	1 2
	2 3
	1 3
	1 5
	0 0

样例输出

	1 4 2 5 3
 /*
问题 给出变量的个数n和m个二元组,输出任意一个从小到大的排序
解题思路 由题中所给的m个二元组可以得到每个点的入度,创建一个队列,先将入度为0的点加入队列,
然后依次出队,出队过程中将以该点为起点的那条边的终点的入度减去1,如果该点的入度变为0,就将该点也加入队列,
直到队列为空。 如果队列为空后,出队的点的个数等于总个数,则说明有拓扑序列,否则说明图内有环,够不成拓扑序列。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std; const int maxn=; vector<int> g[maxn];//表示以g[i]为起点的边,比如表示1——2和1——3这两条边,g[1]中第一个元素为2,第二个元素为3
int rd[maxn];
int topo[maxn]; bool toposort(int n); int main()
{
int m,n,i,u,v,j,flag;
while(scanf("%d%d",&n,&m), n + m != ){
for(i=;i<=m;i++){
scanf("%d%d",&u,&v);
flag=;
for(j=;j<g[u].size();j++)
if(g[u][j] == v)
{
flag=;
break;
}
if(!flag) g[u].push_back(v);
} if(toposort(n)){
for(i=;i<n-;i++)
printf("%d ",topo[i]);
printf("%d\n",topo[n-]);
} for(i=;i<=n;i++)
g[i].clear();
}
return ;
} bool toposort(int n)
{
int i,j;
memset(rd,,sizeof(rd));
for(i=;i<=n;i++){
for(j=;j<g[i].size();j++){
rd[ g[i][j] ]++;
}
} int t=;
queue<int> q;
for(i=;i<=n;i++)
if(rd[i]==){
q.push(i);
} int x;
while(!q.empty()){
x=q.front();
q.pop();
topo[t++]=x;
for(i=;i<g[x].size();i++){
j=g[x][i];
rd[ j ]--; if(rd[j]==)
q.push(j);
}
} if(t==n) return ;
return ;
}
上一篇:Ubuntu 完全卸载MySQL 重装步骤


下一篇:[Android]依赖注入框架google的dagger