Iowa_BattleShip @ 2018-09-19 21:04:24
一个有向图
第一行包含两个整数
应包含两行,第一行包含一个整数
题目描述
一个有向图$G=(V,E)$称为半连通的$(Semi-Connected)$,如果满足:$\forall u,v\in V$,满足$u\rightarrow v$或$v\rightarrow u$,即对于图中任意两点$u,v$,存在一条$u$到$v$的有向路径或者从$v$到$u$的有向路径。若$G^\prime=(V^\prime,E^\prime)$满足$V^\prime\in V$,$E^\prime$是$E$中所有跟$V^\prime$有关的边,则称$G^\prime$是$G$的一个导出子图。若$G^\prime$是$G$的导出子图,且$G^\prime$半连通,则称$G^\prime$为$G$的半连通子图。若$G^\prime$是$G$所有半连通子图中包含节点数最多的,则称$G^\prime$是$G$的最大半连通子图。给定一个有向图$G$,请求出$G$的最大半连通子图拥有的节点数$K$,以及不同的最大半连通子图的数目$C$。由于$C$可能比较大,仅要求输出$C$对$X$的余数。
输入格式
第一行包含两个整数$N,M,X$。$N,M$分别表示图$G$的点数与边数,$X$的意义如上文所述接下来M行,每行两个正整数$a,b$,表示一条有向边$(a,b)$。图中的每个点将编号为$1,2,3\dots N$,保证输入中同一个$(a,b)$不会出现两次。
输出格式
应包含两行,第一行包含一个整数$K$。第二行包含整数$C\mod X$。
@chen_zhe
by Iowa_BattleShip @ 2018-09-20 19:02:25
@chen_zhe
by Iowa_BattleShip @ 2018-09-26 14:27:41
@chen_zhe
by ysner @ 2018-10-10 21:16:17
@chen_zhe
by BalanceUhen @ 2018-10-30 08:01:46
如上文所述接下来M行
by BalanceUhen @ 2018-10-30 08:04:04
@chen_zhe
by agicy @ 2019-01-24 20:16:37
@chen_zhe
by MiaoZ @ 2019-02-24 15:19:46
@chen_zhe
by 小菜鸟 @ 2019-04-27 14:42:08
@chen_zhe
by Y15BeTa @ 2019-10-14 17:36:09
@chen_zhe
by Doubleen @ 2019-12-16 13:30:51
@NaCly_Fish