1514：【例 2】最大半连通子图

题目描述

一个有向图 $G=(V,E)$ 称为半连通的 (Semi-Connected)，如果满足：$\forall u,v \in V$，满足 $u \to v$ 或 $v \to 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$ 的余数。

输入格式

第一行包含三个整数 $N, M, X$。$N, M$ 分别表示图 $G$ 的点数与边数，$X$ 的意义如上文所述；

接下来 $M$ 行，每行两个正整数 $a, b$，表示一条有向边 $(a,b)$。

图中的每个点将编号为 $1,2,3,\cdots,N$，保证输入中同一个 $(a,b)$ 不会出现两次。

输出格式

输出两行。第一行包含一个整数 $K$，第二行包含整数 $C \bmod X$。

样例

样例输入 #1

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

样例输出 #1

3
3

样例解释 #1

• $N=6$ 个点，$M=6$ 条有向边，$X=20070603$。
• 边：
  1. $1 \to 2$
  2. $2 \to 1$
  3. $1 \to 3$
  4. $2 \to 4$
  5. $5 \to 6$
  6. $6 \to 4$
• 图 $G$ 的强连通分量：
  • 分量 $A$：$\{1,2\}$（因为 $1 \leftrightarrow 2$）
  • 分量 $B$：$\{3\}$
  • 分量 $C$：$\{4\}$
  • 分量 $D$：$\{5,6\}$（$5 \leftrightarrow 6$？只有 $5 \to 6$，没有 $6 \to 5$，所以不是强连通，但 $6 \to 4$ 且 $4$ 不能到 $6$，所以 $5$ 和 $6$ 各自为单独的强连通分量？需要运行 Tarjan）。
  • 实际上，$5$ 和 $6$ 之间只有 $5 \to 6$，不能互相到达，所以它们是不同的强连通分量。
• 缩点后得到 DAG，求最大半连通子图（即最长链的节点数及其方案数）。
• 样例中最大半连通子图节点数 $K=3$，可能的一种是 $\{1,2,3\}$ 或 $\{1,2,4\}$ 等，但注意必须满足半连通性（任意两点可达或反向可达）。$\{1,2,3\}$ 中 $3$ 不能到 $1$ 或 $2$，但 $1$ 能到 $3$，所以是半连通的。类似 $\{1,2,4\}$ 也满足。$\{5,6,4\}$ 中 $5$ 不能到 $4$（$5\to6\to4$ 是可达的），且 $4$ 不能到 $5$，所以不满足半连通。
• 最大节点数为 $3$，方案数 $C=3$（可能是 $\{1,2,3\}$、$\{1,2,4\}$、$\{2,1,3\}$？但后两者与第一个可能是同一导出子图？注意集合相同但顺序不同不算不同子图）。实际上 $C=3$ 需要根据算法得出。

数据范围

• 对于 $20\%$ 的数据，$N \le 18$；
• 对于 $60\%$ 的数据，$N \le 10^4$；
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le M \le 10^6$，$X \le 10^8$。

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题需要先进行强连通分量缩点（因为一个强连通分量内的点相互可达，可以视为一个整体），然后在得到的 DAG 上求最大节点数的半连通子图（即最长链，因为 DAG 中半连通子图对应一条链）。需要注意去重边（因为缩点后可能有重边，会影响方案计数）。可以使用拓扑排序动态规划求解：$dp[u]$ 表示以 $u$ 为终点的最大节点数，$ways[u]$ 表示对应的方案数。转移时要注意从不同的前驱转移，且去重边。由于 $M$ 较大，需要用邻接表存储，并注意常数优化。