拓扑排序

​​题目链接​​。题目大意：一个很实际的问题，比赛中只知道两两参赛者的胜负，确定总的胜负。这个问题其实有很多中写法，模拟也是可以的。但是最经典的写法我觉得还是使用拓扑排序来做。

图的拓扑排序其实就是给图的每一个顶点编号，使用一种规则将图的顶点有序的输出，这就是图的拓扑排序。这是对有向无环图来说的，其实这个应用有很多种，比如图的判环，只有无环图才能完成拓扑排序。又比如时间的安排，比赛名次的确定，实际上我们都知道，对于完成一件事情可以分解成不同的小的步骤，这些小的步骤的完成也是有先后顺序的。比如我们必须先穿完裤子再穿鞋子等等。利用这种关系我们可以建图，然后对图进行拓扑排序就可以知道每一个事情的先后顺序。拓扑排序思想很简单主要分为两步:(1)在图中的每一个顶点中寻找入度为0的点，删除这个点的所有边。（2）重复（1）整张图被删除。

下面出给这个具体实现的代码以及必要的解释：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 600;
int M[maxn][maxn];
int in[maxn];//入度数组
int ans[maxn];
int n, m;
void init()
{
memset(M, 0, sizeof(M));
memset(in, 0, sizeof(in));
memset(ans, 0, sizeof(ans));
}
void solve()
{
init();
int x, y;
for (int i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
if (M[x][y] == 0)//这里需要考虑重边的情况
{
in[y]++;
M[x][y] = 1;
}
}
for (int i = 1; i <= n; i++)
{
int k = 1;
while (in[k] != 0)k++;//寻找当前入度为0的顶点
ans[i] = k;//这个时候ans=k
in[k] = -1;//删除这这个顶点
//删除与这个顶点相连的所有边
for (int i = 1; i <= n; i++)
{
if (M[k][i] == 1)
{
in[i]--;
}
}
}
for (int i = 1; i < n; i++)
{
printf("%d ", ans[i]);
}
printf("%d\n",ans[n]);
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
solve();
}
return 0;
}