图论中的圈与块图论中的圈与块绍兴县柯桥中学 黄劲松基本概念w圈(环)w割点w割边(桥)w块w强连通子图(强连通分量(支,块)1/9/20232浙江省2006年集训讲义圈及其相关知识wMST(最小生成树)另类算法w最小环问题1/9/20233浙江省2006年集训讲义MST另类算法w任意构造一棵原图的生成树，然后不断的添边，并删除新生成的环上的最大边。1017253算法证明算法证明?1/9/20234浙江省2006年集训讲义水管局长(1)w给定一张带权无向连通图，定义max(p)为路径p上的最大边，min(u,v)为连接u和v的所有路径中，max(p)的最小值。动态的做如下两个操作：1：询问某两个点之间的min(u,v)2：删除一条边w你的任务是对于每个询问，输出min(u,v)的值。(WC2006)1/9/20235浙江省2006年集训讲义水管局长(2)w数据范围约定结点个数N1000图中的边数M100000询问次数Q100000删边次数D50001/9/20236浙江省2006年集训讲义水管局长(3)w根据kruskal算法可以知道，最小生成树上的连接两点之间的唯一路径一定是最大边最小
