题目大意
给定一个 $n$ 个点 $m$ 条边的无向连通图，你要选择若干个关键点，使得在图中任意删除一个点后（可以删除任何点），图中剩余的点都可以到达某一个关键点。
数据范围：$n, m \le 10^6$。
思路分析
根据割点的定义，发现只有删掉割点才会使某两个结点不联通。所以在一个点双连通分量内部，我们只需要任意选一个点即可。但是并不是所有的点双连通分量都需要选。我们考虑根据割点建一棵树，一个点双连通分量向与之相邻的割点连一条边。这样我们得到了一个割点和点双连通分量相间的树。发现只需要度数为 $1$ 的点双连通分量选上即可，因为树上删掉任意一个点，剩下的所有结点肯定可以跑到某个度数为 $1$ 的点；如果有一个度数为 $1$ 的点没选，那么我们只需删掉与它相邻的那个点即可让这个点无法走到一个关键点。于是我们使用 Tarjan 跑割点，然后将建好的树上度数为 $1$ 的点的 $\text{size}$ 相乘即可。时间复杂度 $O(n + m)$。
你交了上去，发现 WA 了。原因是有一个特殊情况：没有割点。这样你必须选两个点才可行，因为如果只选一个点而那个点被删除了，就不剩下任何关键点了。这样的方案数是 $\binom{n}{2}$。特判一下就可以通过此题了。
实现的时候我们其实不需要把树给建出来，我们只需要对于每一个结点 DFS 出去，找与它所在的联通块相邻的割点个数即可。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | typedef long long ll; |
6 | const int maxn = 1e6; |
7 | int T, n, m, tm, dfn[maxn + 3], low[maxn + 3], cc, sz, vis[maxn + 3]; |
8 | bool cut[maxn + 3]; |
9 | vector<int> G[maxn + 3]; |
10 | |
11 | void add(int u, int v) { |
12 | G[u].push_back(v); |
13 | } |
14 | |
15 | void tarjan(int u, bool is_rt = true) { |
16 | dfn[u] = low[u] = ++tm; |
17 | int son = 0; |
18 | for (int i = 0, v; i < G[u].size(); i++) { |
19 | v = G[u][i]; |
20 | if (!dfn[v]) { |
21 | tarjan(v, false); |
22 | low[u] = min(low[u], low[v]); |
23 | if (!is_rt && low[v] == dfn[u]) { |
24 | cut[u] = true; |
25 | } |
26 | son++; |
27 | } else { |
28 | low[u] = min(low[u], dfn[v]); |
29 | } |
30 | } |
31 | if (is_rt && son >= 2) { |
32 | cut[u] = true; |
33 | } |
34 | } |
35 | |
36 | void dfs(int u) { |
37 | vis[u] = tm; |
38 | sz++; |
39 | for (int i = 0, v; i < G[u].size(); i++) { |
40 | v = G[u][i]; |
41 | if (vis[v] != tm) { |
42 | if (cut[v]) { |
43 | cc++; |
44 | vis[v] = tm; |
45 | } else { |
46 | dfs(v); |
47 | } |
48 | } |
49 | } |
50 | } |
51 | |
52 | int main() { |
53 | while (scanf("%d", &m), m) { |
54 | for (int i = 1; i <= n; i++) { |
55 | G[i].clear(), vis[i] = 0; |
56 | dfn[i] = 0, cut[i] = false; |
57 | } |
58 | n = 0; |
59 | for (int i = 1, u, v; i <= m; i++) { |
60 | scanf("%d %d", &u, &v); |
61 | n = max(n, u), n = max(n, v); |
62 | add(u, v), add(v, u); |
63 | } |
64 | tm = 0; |
65 | tarjan(1); |
66 | tm = 0; |
67 | int res = 0; |
68 | ll ans = 1; |
69 | for (int i = 1; i <= n; i++) { |
70 | if (!cut[i] && !vis[i]) { |
71 | cc = 0, sz = 0, ++tm; |
72 | dfs(i); |
73 | if (cc == 1) { |
74 | res++, ans *= sz; |
75 | } |
76 | } |
77 | } |
78 | printf("Case %d: ", ++T); |
79 | if (res == 0) { |
80 | printf("2 %lld\n", 1ll * n * (n - 1) / 2); |
81 | } else { |
82 | printf("%d %lld\n", res, ans); |
83 | } |
84 | } |
85 | return 0; |
86 | } |