修正题面的符号问题,顺便补LaTeX

P2272 [ZJOI2007] 最大半连通子图

Iowa_BattleShip @ 2018-09-19 21:04:24

题目描述

一个有向图G=(V,E)称为半连通的(Semi-Connected),如果满足:\forall u,v\in V,满足u\rightarrow vv\rightarrow u,即对于图中任意两点u,v,存在一条uv的有向路径或者从vu的有向路径。若G^\prime=(V^\prime,E^\prime)满足V^\prime\in VE^\primeE中所有跟V^\prime有关的边,则称G^\primeG的一个导出子图。若G^\primeG的导出子图,且G^\prime半连通,则称G^\primeG的半连通子图。若G^\primeG所有半连通子图中包含节点数最多的,则称G^\primeG的最大半连通子图。给定一个有向图G,请求出G的最大半连通子图拥有的节点数K,以及不同的最大半连通子图的数目C。由于C可能比较大,仅要求输出CX的余数。

输入格式

第一行包含两个整数N,M,XN,M分别表示图G的点数与边数,X的意义如上文所述接下来M行,每行两个正整数a,b,表示一条有向边(a,b)。图中的每个点将编号为1,2,3\dots N,保证输入中同一个(a,b)不会出现两次。

输出格式

应包含两行,第一行包含一个整数K。第二行包含整数C\mod X

题目描述

一个有向图$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行\Rightarrow如上文所述接下来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


| 下一页