• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1523 – SPF

    ACM-POJ EXP 190阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给定一个连通网络,网络的结点数<=1000,求出这个网络的所有割点编号,并求出若删去其中一个割点k后,对应的,原网络会被分割为多少个连通分量?

    解题思路

    首先要明白什么是割点,什么是连通分量离散数学的知识。

    1、【割点】

    在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合。当割点集合的顶点个数只有1个时,该顶点就是割点。

    2、【连通分量】

    当删除某个割点后,原图会被划分为若干个互不连通的子图,这些子图就是该割点对应的连通分量。


    为了方便下文说明,现在首先说几个小定义。

    如左图G结点4开始进行DFS,会得到右边的深搜树,其中红色边在DFS过程中没有经历过,成【后向边】,其他边称为“树边”。

    由于DFS有搜索次序,首先被搜索的结点其深度deep也越浅,因此【搜索的深度】也称为【时间戳】。

    在深搜树上方的结点,就是下方结点的祖先,显然,【祖先的辈分越高,其深度越浅】。而【后向边】则可用于寻找【辈分更高的祖先】。


    此时,我们可以得到割点的定义如下:

    若有k的儿子为i,我们定义AnceDeep[i]为结点i辈分最高(深度最浅)的祖先的深度,deep[k]为k的搜索深度(时间戳),那么k为割点当且仅当k满足(1)(2)中的一个:

    (1)若k为深搜树的根Root,当且仅当k的儿子数(分支数)>=2时k为割点;

    (2)若k为搜索树的中间结点(即k既不为根也不为叶),那么k必然有father和son,若AnceDeep[son]>= deep[k],则k必然为割点。

    对于(1)是显然的,根结点k一旦有2个以上的分支,那么删除k必然出现森林;

    对于(2)比较难理解,首先注意AnceDeep[son]>= deep[k]这个条件,意思就是“k的儿子son的辈分最高的祖先(暂且设其为w)的深度,比k的深度要深(或者等于k的深度,此时k就是w),就是说k的辈分比w更高(深度更浅),那么一旦删除k,son所在的网络势必和 k的father所在的网络断开”,那么k就是割点。


    当了解了上述知识之后,就可以参考刘汝佳的《算法艺术与信息学竞赛》P285所述的求割点的方法。当然你可以用tarjan算法,但是不怎么好理解,初入门的同学我还是建议你先用刘汝佳的方法熟悉一下求割点,再学tarjan算法就不难了。

    注意刘汝佳的算法模板中,她的Ancestor[]就是我上文提及的AnceDeep[];她的D[]就是我上文提及的deep[];她的Tot就是我上文提及的son;她的deep就是时间戳,即搜索深度,我在程序中定义为depth,DFS时每入栈一次,depth+1,退栈一次depth-1。

    下面贴图就是刘汝佳求割点的算法

    求出所有割点后,剩下的就是求出某个割点对应的连通分量数。这个比较好办。首先要明白,因为删除割点后,与该割点相连的边也会被删除,那么割点对应的连通分量数必定小于等于该割点的分支数,这是因为割点的某几个看似互不相连的分支,可能又在什么地方连接起来了。

    那么要知道删除某个割点后所得到连通分量数,只需要对原图G所有结点做一个vist标记,初始化为false,割点的vist初始化为true。从割点出发,枚举该割点的所有分支,对每条分支做一次DFS,搜索并标记该分支所在的连通分量上的所有结点。

    例如当在DFS第i个割点分支时,vist为false的结点访问并标记为true,vist已经为true的则不可访问,按照这种规律搜索,当返回到割点时,说明该分支所在的连通分量的所有结点已被标记访问。

    然后DFS第i+1个分支,若该分支结点已经为true,说明它和第i个分支(或此前DFS的某个分支)是在同一个连通分量的,则无需DFS,直接DFS第i+2的分支。

    那么需要DFS的分支数就是所求的删除该割点后的连通分量数。

    最后建议

    1、 用邻接表存储图。

    2、注意输入输出格式,尤其是每组数据的“两个空格”和“一个空行”,以免PE。

    3、测试数据并所给出的编号并不一定是从编号1开始的,因此一开始就应该开辟1000个(最大结点数)的存储空间,以免RE。

    Source修正

    Greater New York 2000 – 问题H

    测试数据

    本文第二页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ1523 – SPF

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址