HDU1285 - 确定比赛名次 - 拓扑排序模板题
WA代码
这个是按照自己的理解写的，样例过了，可是WA：
#include
#include
#include
#include
using namespace std;
int a[550][550];
int rudu[550];
int ans[550];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(a,0,sizeof(a));
memset(rudu,0,sizeof(rudu));
memset(ans,0,sizeof(ans));
int aa,bb;
for(int i=0; i WA的原因
如果碰到1 2、1 2出现两次及多次的时候，按照错误的代码2会被加两次，而实际只需要加一次入度即可。所以相当于标记和未标记两种情况，而不需要多次去进行 ++ 操作。
AC代码
这个是后来周赛结束改的AC了：
#include
#include
#include
#include
using namespace std;
int a[550][550];
int rudu[550];
int ans[550];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(a,0,sizeof(a));
memset(rudu,0,sizeof(rudu));
memset(ans,0,sizeof(ans));
int aa,bb;
for(int i=0; i 拓扑排序知识点
正好整理一下拓扑排序入门的知识点：
拓扑排序的优点及适用场景：
快速排序是不稳定的，这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。如果用偏序的概念可以这样解释这一现象：相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。
而对于诸如插入排序这种稳定性排序，它们对于值相同的元素，还有一个潜在的比较方式，即比较它们的出现顺序，出现靠前的元素大于出现后出现的元素。因此通过这一潜在的比较，将偏序关系转换为了全序关系，从而保证了结果的唯一性。而拓扑排序就是一种将偏序转换为全序的一种算法。
补充两个概念，偏序和全序：
偏序：有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。
全序：就是在偏序的基础之上，有向无环图中的任意一对顶点还需要有明确的关系(反映在图中，就是单向连通的关系，注意不能双向连通，那就成环了)。
意思就是讲，一个不确定的偏序关系经全序后就有一种确定的先后顺序了。
既然有先后，那么在实际生活中的选课问题，比如大一时一定要修完这门课，大二才学第二门课，这种排课问题就是拓扑排序问题。
总结以上，拓扑排序实质上就是一种偏序到全序的排序算法。
定义：
只有有向无环图(Directed Acyclic Graph，简称DAG )才有拓扑排序。
DAG必至少有一个入度为零的点和一个出度为零的点。
wikipedia中关于拓扑排序的定义：在拓扑排序中，对于任意一个有向边的起点和终点，在排序后起点总是在终点前。
在DAG中如果对于任意两点都可以找到一条路径使二者连通，则称该图是全序的，否则为偏序。
全序DAG的拓扑排序是该图的一条哈密顿路径，即经过该图的所有顶点。
算法：常用的有Kahn算法和DFS算法。
参考
附上我入门拓扑排序看的文章：
https://blog.csdn.net/qq_41713256/article/details/80805338