【拓扑排序】HDU 1285——确定比赛名次

来源：点击打开链接

做完这道题，可以对无环图的拓扑排序有所了解。

无前驱的顶点优先的拓扑算法主要分为三步：

1、找到一个入度为0的顶点并且输出之。

2、在图中删除该顶点，并且删除与该顶点有关的边。

3、重复步骤（1）（2），直到剩余的网中不存在没有前驱的顶点。

这个题点集比较集中，可以采用邻接矩阵的形式。

#include <iostream>#include <cstring>#include <iostream>using namespace std;int mat[505][505];int indegree[505];int ans[505];int main(){    int length,match;    while(cin>>length>>match)    {        memset(ans,0,sizeof(ans));        memset(indegree,0,sizeof(indegree));        memset(mat,0,sizeof(mat));        int x,y;        for(int i=0;i<match;i++)        {            cin>>x>>y;            mat[x][y]=1;        }        for(int i=1;i<=length;i++)        {            for(int j=1;j<=length;j++)            {                if(mat[i][j])                   indegree[j]++;            }        }        for(int i=1; i<=length; i++)        {            int k=1;            while(indegree[k]!=0)                k++;              ans[i]=k;            indegree[k]--;//更新为-1，后边检测时不受影响            for(int j=1; j<=length; j++)                if(mat[k][j])                     indegree[j]--;//相关联的入度减1        }                for(int i=1;i<length;i++)            cout<<ans[i]<<" ";           cout<<ans[length]<<endl;            }        return 0;}