拓扑和传递闭包小结

时间:2021-09-28 22:39:38

拓扑排序与传递闭包

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=71575#overview

这几天主要学了一下拓扑排序,同时还在题目中遇到了解决传递闭包的warshell算法。

首先简单总结一下拓扑排序的东西,目前掌握了三种拓扑排序的算法:刘汝佳算法竞赛书上的一种(这种并不是很常用,但是很巧妙,主要是学习一下那种思想);第二种是自己用vector写的dfs算法,它在处理一些优先队列问题的时候不是很方便,所以当时写RankofTetris这道题的时候很费劲;最后就是用栈或者队列的写法,这种是最常用也算是最简便的。后两种的思想是一样的:每次寻找入度为零的点,然后处理它的下一个结点。

就目前做的题目来看,拓扑的关键点就是:

  1. 是否有冲突的信息; 当有冲突的时候就会形成环,所以就没法遍历到,因此记录遍历的总数与结点总数比较即可。

  2. 判断信息是否完整;即判断每个点的关系是否确定,若每个点的关系都确定,那么每次进栈的元素个数都唯一。如果要判断有多少的点的顺序唯一确定,就用传递闭包,判断每个点和其它点的关系都确定CowContest

  3. 有时候处理相等的元素要用并查集。

  4. 有时候加一个源点会让问题变得简单。

  5. 拓扑排序的一些优先次序问题经常和优先队列联系在一起

经典的好题Rankof Tetris

SortingIt All Out

CowContest cf Conservation