2017-09-12 19:50:58
writer:pprp
最近刚开始接触拓扑排序，拓扑排序适用于：无圈图的顶点的一种排序，
用来解决有优先级别的排序问题，比如课程先修后修，排名等。
主要实现：用矩阵来储存图，用indegree数组记录每个顶点的入度，
从入度为0的开始，每次删除该入度为0的点，然后修改其他顶点的入度，
在进行查找入度为0的顶点，循环下去就可以
题意如下：给你n个队伍，m个优先顺序，让你输出总的排名的优先顺序。
代码如下:
/*
@theme:拓扑排序 hdu 1285
@writer:pprp
@declare: accepted
@begin:19:00
@end:19:47
@error:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 518;
bool G[maxn][maxn];
int ans[maxn];
int indegree[maxn];//存取入度
int n, m;
void init()
{
memset(indegree,0,sizeof(indegree));
memset(ans,0,sizeof(ans));
memset(G,0,sizeof(G));
}
void toposort()
{
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ;j <= n ;j++)
{
if(G[i][j])
indegree[j]++;
}
}
//应该从入度为0的开始
for(int i = 1; i <= n;i++)
{
int k = 1;
while(indegree[k]!=0)
k++;
ans[i] = k;
//删除根节点
indegree[k] = -1;
for(int j = 1; j <= n; j++)
{
if(G[k][j])
indegree[j]--;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
int x, y;
while(cin >> n >> m)
{
init();
for(int i = 0 ; i < m ;i++)
{
cin >> x >> y;
G[x][y] = 1;
}
toposort();
for(int i = 1; i < n; i++)
cout << ans[i] << " ";
cout << ans[n] << endl;
}
return 0;
}
原文：http://www.cnblogs.com/pprp/p/7511916.html