NeoRuTayE's blog

ACM图论 最小生成树并查集树上求所有点对的距离的和dfskruskal

HDU2376 & HDU5723

2019-04-22

(封面图与内容完全无关，只是因为图好看才放上来)

Rank of Tetris 根据题单的提示，这是一道拓补排序+并查集的题目，然而我并不会拓补排序......所以这里先写一下拓补排序相关的东西吧...... 首先，拓补排序是对一系列有先后顺序的“活动”的排序。何为“有先后顺序的‘活动’”？举个例子，假如现在某人要穿衣服，那他必须要先穿内衣再穿中间的毛衣，最后再穿外套。拓补排序就是使用有向无环图(DAG)来对这些有先后顺序的活动进行排序，得到一个可行的顺序。对于同一系列的活动，可能有多于一种顺序可以使他们满足拓补排序。这跟穿衣服时可以先穿裤子再穿毛衣然后再穿外套，也可以先穿毛衣再穿裤子然后穿外套是一样的。拓补排序的实现：先找出入度为0的点，然后将这个点以及与这个点相连的边删除，并将与这个点直接相连的点的入度都减一。再找出当前入度为0的点，重..

ACMC C++图论 并查集