最小树形图算法
最小树形图
给定一副有向图，选定某个特定的结点作为根，我们希望能找到一株树，树中所有顶点对于根是可达的，且从根到每个顶点的路径都是唯一的，这样的图称为树形图。
对于所有这类树形图中，总边权最小的为最小树形图。
朱刘算法
我们找到每个顶点（除了根）的最小权入边找到，假如这些边组成的树是无环树，可以证明这是一个最小树形图。实际上在这样一个无环树中，从任意一个顶点沿着反向边移动，最后一定会抵达根。而最小是很显然的，因为不存在更小的。
当然假如运气没那么好，我们就需要一些额外操作了。
命题1：如果由最小权入边组成的树中有环，设环的长度为k，那么可以保证至少存在一个最小树形图，包含该环中k-1个边。
假设最小树形图中离根最近（即从根出发到该顶点经过边数最少）的环上顶点为u，很显然u的最小权入边不包含于树形图中。但是对于环上的边$(u,v)$，如果不存在树形图中，我们可以切断v与父亲的边，而加入$(u,v)$，而新图总权不会增大。不断这样操作，就可以将另外$k-1$条边都加入到图上。
我们可以将环合并为一个顶点，所有进入环内顶点的边的目的地修改为合并后的顶点，同时对于某个顶点v的入边，其权值还需要减去v的最小权入边的权，因为当选择这条边加入最终结果时，会断开v的最小权入边。
由于命题1的存在，我们保证我们得到的树形图中，保护环上的k-1条边，换言之，我们可以认为环上的顶点始终是连通的，因此合并为一个顶点并不会影响最终结果（其只能接受一个入边且始终连通），我们可以将其作为一个顶点处理。并在缩点后的图上重复调用这个流程，直到所有不存在环。
假如最终图除了根以外，还存在其余顶点没有最小权入边，那么就不存在树形图，否则就找到了树形图。
可以通过并查集找环，最多发生$V-1$此缩环，每次找环最多$O(E)$时间复杂度，因此总的时间复杂度为$O(VE)$。
Tarjan的最小树形图算法
详细的可以见课件。
Tarjan提供了朱刘算法的快速实现方案，预处理的时间复杂度为$O(E\log_2V)$。之后可以多次以$O(V)$的时间复杂度找到以任意顶点为根的最小树形图。
下面讲一下我的实现方案。（这里并非是Tarjan的原来版本，只不过是我自己为了方便实现的设计）
首先我们必须保证图的连通性，即任意两个顶点之间都有互相抵达的路径。我们可以加入O(V)条边，将所有顶点串成一个环，并设置这些边的权为无穷，保证这些边不会被用来组成最小树形图即可。
我们维护一个栈，一开始任意选择一个顶点加入到栈中。之后执行下面流程：
1.如果所有顶点都缩为了一个顶点，则结束流程，否则进入步骤2。
2.为栈尾元素v找到最小入边（可以为每个顶点的入边维护一个最小堆），如果最小入边是自环，那么就找下一个，直到找到非自环的边（这里一定是可以成立的，因为我们一开始就保证了图的连通性）。
2.记边的起点为u，所在并查集的currentLevel为x。我们记录v.inEdge为边$(u,v)$。
3.如果x不曾被加入过栈中，我们将x加入栈中，并将x.outEdge设置为边$(u,v)$。之后回到步骤1。
4.新建一个新的结点代表整个环，记作q，将q.outEdge设置为x.outEdge，x.outEdge设置为$(u,v)$。将栈尾元素t和q所在并查集合并。同时需要将最小堆合并，我们这里可以采用可合并堆，我用的是左偏树，你们任意。合并之前，不要忘了将t的整个左偏树中的边的权减少t.inEdge的权值，这里可以使用惰性标记来保证$O(1)$的时间复杂度。之后将t.parent设置为q，并设置t.outNode为环上前一个元素（一般是栈前一个元素，对于x则是v）。不断退栈重复该过程，直到x出栈。
5.将q所在并查集的currentLevel设置为q。将q入栈。回到步骤1。
contract(V, E){
remain = |V|;
stack.push(one node in V);
while(remain > 1){
tail = stack.peek();
minInEdge = null;
while(true){
minInEdge = tail.queue.remove();
if(minInEdge.src.find() != minInEdge.dst.find()){
break;
}
}
x = minInEdge.src.find().currentLevel;
if(!x.visited){
x.visited = true;
stack.push(x);
x.outEdge = minInEdge;
continue;
}
q = new node;
q.visited = true;
q.outEdge = x.outEdge;
x.outEdge = minInEdge;
last = x;
while(true){
t = stack.pop();
t.queue.modify(-last.outEdge.weight);
q.queue = mergeQueue(q.queue, t.queue);
mergeDUS(q, t);
t.parent = q;
last.outNode = t;
last = t;
remain--;
if(t == x){
break;
}
}
q.find().currentLevel = q;
stack.push(q);
remain++;
}
top = stack.pop();
}
上面的步骤就是预处理的流程。我们知道每次创建合并顶点，图上的顶点总数必定至少减1，因此整个流程处理的顶点总数仅为$O(V)$。步骤2最多执行$O(E)$次，每次时间复杂度为$O(\log_2V)$（来自同一顶点的入边可以仅保留最小权的那个）。步骤3每次都会往栈中加入一个未被标记的顶点，这些顶点一定是原来图上的顶点（不是合并后的顶点），因此最多执行$O(V)$次。步骤4的每次合并，都会减少图上只少一个顶点，因此合并最多发生$O(V)$此。而左偏树的合并的时间复杂度为$O(\log_2V)$。
因此加总后可以发现总的时间复杂度为$O(E\log_2V)$。
下面要说的是如何基于预处理，从中抽取出以顶点r为根的最小生成树。一般的思路是从上往下剖开最后缩成的合并顶点，但是tarjan版本则使用了从底至上的方案。我们将预处理阶段留在栈中的唯一顶点记作top。
1.如果r已经被标记或者r为top，则返回。
2.标记r所在的环上的所有顶点。并将除了r在环上的最小入边外其余所有环上的边加入到结果中。
3.通过outNode属性遍历环上的所有顶点x，并通过outEdge的终点这个属性，找到x代表的子树中的根y，对y调用这个流程。
4.对r.parent调用这个流程。
因为每次调用这个流程，或者循环的过程中，都会至少标记一个新的顶点，每个顶点仅会被标记一次。整个图中剩下$O(V)$个顶点和$O(V)$条边，因此总的时间复杂度为$O(V)$。
dismantle(r, result){
if(r == top || r.visited){
return;
}
r.visited = true;
trace = r;
while(true){
front = trace.outNode;
frontRoot = trace.outEdge.dst;
if(front == r){
break;
}
front.visited = true;
dismantle(frontRoot, result);
result.add(trace.outEdge);
trace = front;
}
dismantle(r.parent);
}
提供一道练习用的题目LUOGU4716。