HBC20218[JSOI2015]最小表示题解

天涯离梦残月幽梦 算法基础篇 51 0
全网最全C++题库,助您快速提升编程技能!题库丰富多样,涵盖各个领域,让您在练习中不断成长!
还记得去年JYY所研究的强连通分量的问题吗?为了简化一下大家的工作量,这次JYY保证他给定的有向图一定是一个有向无环图。

【故事背景】 还记得去年JYY所研究的强连通分量的问题吗?去年的题目里,JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的JYY,今年又琢磨起了“删边”的问题。  【问题描述】 对于一个N个点(每个点从1到N编号),M条边的有向图,JYY发现,如果从图中删去一些边,那么原图的连通性会发生改变;而也有一些边,删去之后图的连通性并不会发生改变。 JYY想知道,如果想要使得原图任意两点的连通性保持不变,我们最多能删掉多少条边呢?  为了简化一下大家的工作量,这次JYY保证他给定的有向图一定是一个有向无环图(JYY:大家经过去年的问题,都知道对于给任意有向图的问题,最后都能转化为有向无环图上的问题,所以今年JYY就干脆简化一下大家的工作)。

HBC20218[JSOI2015]最小表示题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
想要在职场中立于不败之地?那就来试试全网最全C++题库,让您在练习中快速提升技能。

标签: HBC20218[JSOI2015]最小表示题解