信息学一本通,图论2422: 信息学奥赛一本通T1514-最大半连通子图题解

回忆凄美了谁 算法基础篇 69 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
一个有向图 G=(V,E) 称为半连通的 ,如果满足:u,v∈V,满足 u→v或 v→u,即对于图中任意两点 u,v,存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径,给定一个有向图 G,请求出 G 的最大半连通子图拥有的节点数 K,以及不同的最大半连通子图的数目 C,由于 C 可能比较大,仅要求输出 C 对 X 的余数。

原题来自:ZJOI 2007 一个有向图 G=(V,E) 称为半连通的 (Semi-Connected),如果满足:∀u,v∈V,满足 u→v或 v→u,即对于图中任意两点 u,v,存在一条 u 到 v 的有向路径或者从 v 到 u 的有向路径。 若 G'=(V',E') 满足,E' 是 E 中所有和V' 有关的边,则称G' 是 G 的一个导出子图。若 G' 是 G 的导出子图,且 G' 半连通,则称 G' 为 G 的半连通子图。若G' 是 G 所有半连通子图中包含节点数最多的,则称 G' 是 G 的最大半连通子图。 给定一个有向图 G,请求出 G 的最大半连通子图拥有的节点数 K,以及不同的最大半连通子图的数目 C。由于 C 可能比较大,仅要求输出 C 对 X 的余数。

信息学一本通,图论2422: 信息学奥赛一本通T1514-最大半连通子图题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: 信息学一本通 图论2422: 信息学奥赛一本通T1514-最大半连通子图题解