1525：电力

题目描述

原题来自：CTU Open 2004

求一个图删除一个点之后，连通块最多有多少。

输入格式

多组数据。第一行两个整数 $P, C$ 表示点数和边数。

接下来 $C$ 行每行两个整数 $p_1, p_2$，表示 $p_1$ 与 $p_2$ 有边连接，保证无重边。读入以 0 0 结束。

输出格式

输出若干行，表示每组数据的结果。

样例

样例输入 #1

3 3
0 1
0 2
2 1
4 2
0 1
2 3
3 1
1 0
0 0

样例输出 #1

1
2
2

样例解释 #1

第一组数据：

• $P=3, C=3$。
• 边：$(0,1), (0,2), (2,1)$。
• 图是一个三角形（完全图 $K_3$），删除任意一个点后，剩下两个点仍然相连，连通块数为 $1$（即剩余图连通）。
• 输出 $1$。

第二组数据：

• $P=4, C=2$。
• 边：$(0,1), (2,3)$。
• 图有两个连通分量：$\{0,1\}$ 和 $\{2,3\}$。
• 删除一个点后：
  • 如果删除 $0$ 或 $1$，则第一个分量变成单个点，第二个分量不变，连通块数为 $2$（单个点也算一个连通块）。
  • 如果删除 $2$ 或 $3$，类似得到 $2$。
• 最大连通块数为 $2$。

第三组数据：

• $P=3, C=1$。
• 边：$(1,0)$。
• 图是一条链 $1-0$，还有一个孤立点 $2$（因为点编号从 $0$ 到 $P-1=2$，点 $2$ 没有边）。
• 删除一个点后：
  • 删除 $0$：剩下点 $1$ 和点 $2$，两个孤立点，连通块数 $2$。
  • 删除 $1$：类似，连通块数 $2$。
  • 删除 $2$：剩下点 $0$ 和点 $1$ 相连，连通块数 $1$。
• 最大连通块数为 $2$。

数据范围

• $1 \le P \le 10000$
• $C \ge 0$
• $0 \le p_1, p_2 < P$

时空限制

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

注意：本题是求无向图中删除一个点后，连通块的最大数量。图可能不连通。对于每个连通分量，删除一个割点可能会增加连通块数量；如果删除的不是割点，则连通块数量不变或减少（因为删除孤立点会减少连通块）。因此，需要求出每个连通分量的割点，并计算删除该割点后增加的连通块数量（即该割点连接的子分量数）。对于整个图，答案 = 原连通块数 + 最大增加量 - 1（因为删除的点本身算一个连通块？需要仔细推导）。具体做法：

1. 用 Tarjan 算法求割点。
2. 对于每个连通分量，设其根节点为 $u$，如果 $u$ 是割点，则删除 $u$ 后增加的连通块数为 $child$（$u$ 在 DFS 树中的子节点数）；如果 $u$ 不是割点，则删除 $u$ 后连通块数增加 $0$。
3. 对于非根割点 $v$，删除 $v$ 后增加的连通块数为满足 $low[to] \ge dfn[v]$ 的子节点 $to$ 的数量。
4. 取所有点中删除后增加的连通块数的最大值 $max\_add$，则答案为 $原连通块数 + max\_add$（注意如果原图只有一个点，则删除后为 $0$ 个连通块？需要特判）。但样例中第二组数据原连通块数为 $2$，$max\_add=0$（因为没有割点），答案为 $2$，符合公式。