图论中的圈与块无向图的最小环.ppt

数据范围约定嗅探器(2)*浙江省2006年集训讲义*01结点个数N≤10002边数M≤N*(N-1)/2嗅探器(3)*浙江省2006年集训讲义*朴素算法：枚举每个点，删除它，然后判断a和b是否连通，时间复杂度O(NM)如果数据范围扩大，该算法就失败了！030102嗅探器(4)*浙江省2006年集训讲义*题目要求的点一定是图中的割点，但是图中的割点不一定题目要求的点。如上图中的蓝色点，它虽然是图中的割点，但是割掉它之后却不能使a和b不连通01由于a点肯定不是我们所求的点，所以可以以a为根开始DFS遍历整张图。02对于生成的DFS树，如果点v是割点，如果以他为根的子树中存在点b，那么该点是问题所求的点。03嗅探器(5)时间复杂度是O(M)的如图，蓝色的点表示问题的答案，黄色的点虽然是图的割点，但却不是问题要求的答案ab关键网线(1)*浙江省2006年集训讲义*01无向连通图中，某些点具有A属性，某些点具有B属性。请问哪些边割掉之后能够使得某个连通区域内没有A属性的点或者没有B属性的点。(CEOI2005)02数据范围约定结点个数N≤100000边数M≤1000000关键网线(2)*浙江省2006年集训讲义*朴素算法：枚举每条边，删除它，然后判断是否有独立出来的连通区域内没有A属性或者没有B属性。复杂度O(M2)当然，这个复杂度太大了！010302关键网线(3)*浙江省2006年集训讲义*正如嗅探器一样，题目要求的边一定是原图中的割边，但是原图中的割边却不一定是题目中要求的边。设A种属性总共有SUMA个，B中属性总共有SUMB个。和嗅探器类似的，如果边e=u→v是割边，且以v为根的子树中，A种属性的数目为0或者为SUMA，或者B种属性的数目为0或者为SUMB，那么e就是题目要求的边。关键网线(4)*浙江省2006年集训讲义*下图中，蓝色的边表示题目要求的边，黄色的边表示虽然是图中的割边，但不是题目要求的边。ABAAAAAAABB块*浙江省2006年集训讲义*没有割点的图叫2-连通图，亦称做块，G中成块的极大子图叫做G的块。把每个块收缩成一个点，就得到一棵树，它的边就是桥。求块的算法*浙江省2006年集训讲义*01在求割点的算法中，当结点u的所有邻边都被访问过之后，如果lowlink[u]=dfn[u]，我们把u下方的整块和u导出作为图中的一个块。02这里需要用一个栈来表示哪些元素是u代表的块。程序代码*浙江省2006年集训讲义*PROCEDUREDFS(v);begin inc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为sign lowlink[v]:=sign;//给lowlink[v]赋初始值 inc(tot);stack[tot]:=v;//v点进栈 for寻找一个v的相邻节点u if边uv没有被标记过then begin 标记边uv; 给边定向v→u; ifu未被标记过then begin DFS(u);//uv是父子边，递归访问程序代码*浙江省2006年集训讲义* lowlink[v]:=min(lowlink[v],lowlink[u]); end else lowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖边 end; iflowlink[v]=dfn[v]then begin 块数目number+1; repeat 标记stack[tot]这个点为number; dec(tot);//点出栈 untilstack[tot+1]=v; end;end;新修公路(1)*浙江省2006年集训讲义*给出一张简单无向图，问最少添加几条边能够使得原图中没有割边。(CEOI2000)数据范围约定结点个数N≤2500边数M≤20000新修公路(2)*浙江省2006年集训讲义*为了简化数据关系，我们先将原图收缩，变成一棵树，容易知道的是，剩下的任务就是添最少的边，使得树成为一个块。(树中的两个结点之间连边相当于原图中两个块中分别任意取点连在一起)猜想：每添一条边，就选择树中的两个叶子结点，将它们连起来，于是最少的添边数目就是(叶子结点个数+1)/2新修公路(3)*浙江省2006年集训讲义*如图所示，点代表了原图中的一个块，它们之间的连边是割边。连接a与c，b与d之后，图中