具有唯一一个“割点源”的标号有向连通图的计数的任务书.docx
上传人:快乐****蜜蜂 上传时间:2024-09-14 格式:DOCX 页数:2 大小:10KB 金币:5 举报 版权申诉
预览加载中,请您耐心等待几秒...

具有唯一一个“割点源”的标号有向连通图的计数的任务书.docx

具有唯一一个“割点源”的标号有向连通图的计数的任务书.docx

预览

在线预览结束,喜欢就下载吧,查找使用更方便

5 金币

下载此文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

具有唯一一个“割点源”的标号有向连通图的计数的任务书任务:给定一个有向连通图,求其割点源的个数。输入:有向连通图,用邻接表表示。输出:割点源的个数。割点源的定义:对于一个有向连通图中的一个点u,如果在删除u时图不再连通,则称u为割点源。示例输入:```4412233441```示例输出:```1```提示:本题可以使用Tarjan算法来求解。具体地,对于图G,从一个任意点开始进行dfs遍历,每访问到一个新的点,将该点的dfs编号和低位函数值记为dfn[u]和low[u]。如果有一条从u出发的树边指向了v,则将low[u]设为min{low[u],dfn[v]}。如果v不是u的父节点,且满足dfn[v]<low[u],则说明(u,v)是割边;如果需要统计割点源,只需要增加一个计数器cut_count,然后在dfs树上对每个非根节点u,统计其子树中是否存在一棵不与u连通的子树,如果存在,则说明u是割点源,将计数器加一即可。