拓扑排序与传递闭包
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=71575#overview
这几天主要学了一下拓扑排序,同时还在题目中遇到了解决传递闭包的warshell算法。
首先简单总结一下拓扑排序的东西,目前掌握了三种拓扑排序的算法:刘汝佳算法竞赛书上的一种(这种并不是很常用,但是很巧妙,主要是学习一下那种思想);第二种是自己用vector写的dfs算法,它在处理一些优先队列问题的时候不是很方便,所以当时写RankofTetris这道题的时候很费劲;最后就是用栈或者队列的写法,这种是最常用也算是最简便的。后两种的思想是一样的:每次寻找入度为零的点,然后处理它的下一个结点。
就目前做的题目来看,拓扑的关键点就是:
-
是否有冲突的信息; 当有冲突的时候就会形成环,所以就没法遍历到,因此记录遍历的总数与结点总数比较即可。
-
判断信息是否完整;即判断每个点的关系是否确定,若每个点的关系都确定,那么每次进栈的元素个数都唯一。如果要判断有多少的点的顺序唯一确定,就用传递闭包,判断每个点和其它点的关系都确定CowContest
-
有时候处理相等的元素要用并查集。
-
有时候加一个源点会让问题变得简单。
-
拓扑排序的一些优先次序问题经常和优先队列联系在一起
经典的好题Rankof Tetris