题目描述
原题来自：ZJOI 2007
一个有向图
G = (V,E)
G=(V,E) 称为半连通的 (Semi-Connected)，如果满足：
\forall u,v\in V
∀u,v∈V，满足
u\to v
u→v 或
v\to u
v→u，即对于图中任意两点
u,v
u,v，存在一条
u
u 到
v
v 的有向路径或者从
v
v 到
u
u 的有向路径。
若
G=(V,E)
G
′
=(V′,E′) 满足，
E
E’ 是
E
E 中所有和
V
V’ 有关的边，则称
G
G’ 是
G
G 的一个导出子图。若
G
G’ 是
G
G 的导出子图，且
G
G’ 半连通，则称
G
G’ 为
G
G 的半连通子图。若
G
G’ 是
G
G 所有半连通子图中包含节点数最多的，则称
G
G’ 是
G
G 的最大半连通子图。
给定一个有向图
G
G，请求出
G
G 的最大半连通子图拥有的节点数
K
K，以及不同的最大半连通子图的数目
C
C。由于
C
C 可能比较大，仅要求输出
C
C 对
X
X 的余数。
输入
第一行包含三个整数
N,M,X
N,M,X。
N,M
N,M 分别表示图
G
G 的点数与边数，
X
X 的意义如上文所述；
接下来
M
M 行，每行两个正整数
a, b
a,b，表示一条有向边
(a, b)
(a,b)。
图中的每个点将编号为
1,2,3,\cdots ,N
1,2,3,⋯,N，保证输入中同一个
(a,b)
(a,b) 不会出现两次。
输出
应包含两行。第一行包含一个整数
K
K，第二行包含整数
C \bmod X
CmodX。
样例输入
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
样例输出
3
3
提示
数据范围与提示
对于
20\%
20% 的数据，
N \le 18
N≤18；
对于
60\%
60% 的数据，
N \le 10^4
N≤104；
对于
100\%
100% 的数据，
1\le N \le 10^5,1\le M \le 10^6,X\le 10^8
1≤N≤105,1≤M≤106,X≤108。
来源/分类
ybttg 图论 DP 拓扑排序