拓扑排序

拓扑排序

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

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

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

#includeusing 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。