把 gcd 为合数翻译成共享「见证数 pq / p²」,在原点加见证数的二部图上跑 Tarjan 求割点子树,逐个点算出删点后的最大连通块。
OJ: roj
题目 ID: 1736
难度:提高+/省选-
标签:图论数论Tarjan割点质因数分解连通块python
创建: 2026-10-07 20:59
更新: 2026-10-07 20:59
形式化题目
给定
要求恰好删除一个点
多组数据,
以题面第一组样例
| 删除 |
|||||
|---|---|---|---|---|---|
| 各连通块大小 | |||||
| 最大块 $ | M(x) | $ |
删掉
正解
思路
第一步:把数论条件换成图论条件。 直接判边需要
- 存在两个不同的质数
同时整除 ,即 ; - 或者存在质数
满足 。
把这两类数统称为见证数:
于是
原图的一条边变成了"两个点共享一个见证数"。
第二步:把共享关系摊成二部图。 建一个二部图
这个转换的关键性质是:
第三步:把"删点"也搬过去。 删掉的是原点。注意见证数点永远不会被删掉,
于是
在
中删去原点 ,使剩余部分(只数原点)的最大连通块最小。
第四步:一次 Tarjan 解决所有
- 根的儿子
满足 : 是割点,删除 后 这棵子树与原连通块剩余部分分开,得到一块大小 ; - 原连通块去掉
与所有被切出的子树后,剩下的部分大小为 ; - 其他连通块不受影响,大小不变。
所以
答案就是 ties 计数就是干这个的)。
复杂度来源。 一个
空间
代码
Python 版(同一算法;为了让 CPython 能跑动顶格数据,额外做了两处不改算法的图压缩: 点权相同且为合数的一批点合成一个权值等于点数的节点,以及剪掉度数只有 1 的见证数节点):
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 20:30
# update_at: 2026-10-07 20:30
import sys
from array import array
from collections import Counter
from math import isqrt
NO_PARENT = -1 # DFS 树的根没有父亲,用它当「无父亲」哨兵
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type NodeList = list[int] # 合并点(代表同值的若干个原点)的权值
type Adj = list[list[int]] # 邻接表:合并点 -> 见证数,见证数 -> 合并点
type Witnesses = list[list[int]] # 每个合并点的见证数节点编号
type PrimePowers = list[tuple[int, int]] # 一个数的质因数分解:(质数, 指数)
type IdMap = dict[int, int] # 见证数 -> 它在二部图里的节点编号
type LowInfo = tuple[list[int], list[int], list[int], list[int], list[int], list[int]] # Tarjan 的 6 张表
def build_spf(limit: int) -> array:
"""筛最小质因子表:spf[x](若为 0 则视为 x)就是 x 的最小质因子。
先埃氏筛出 <= sqrt(limit) 的质数,再**按从大到小**拿每个质数整片覆盖自己的倍数,
于是每个位置最后落地的就是最小质因子;只需 <= sqrt(limit) 的质数,因为合数必有不超过
sqrt 的质因子。因此 x 是质数(或 x < 2)时 spf[x] 仍是 0,调用方用 `spf[x] or x` 补上。
用 array('i') 而不是 list,10⁷ 长度下内存从几百 MB 降到 40 MB。
"""
root = isqrt(limit)
flag = bytearray([1]) * (root + 1)
flag[0:2] = b"\x00\x00"
for i in range(2, isqrt(root) + 1):
if flag[i]:
flag[i * i:: i] = bytearray(len(range(i * i, root + 1, i)))
spf = array('i', bytes(4 * (limit + 1)))
for p in range(root, 1, -1):
if flag[p]:
spf[p:: p] = array('i', [p]) * ((limit - p) // p + 1)
return spf
def prime_powers(x: int, spf: array) -> PrimePowers:
"""把 x 分解成 (质数, 指数) 列表;每轮至少消掉一个质因子。"""
factors = []
while x > 1:
p = spf[x] or x # spf 的 0 是哨兵,含义见 build_spf
e = 0
while x % p == 0:
x //= p
e += 1
factors.append((p, e))
return factors
def witnesses_of(factors: PrimePowers) -> list[int]:
"""x 的见证数集合:与 x 共享见证数 <=> gcd(x, y) 是合数。
见证数取「两个不同质因子的积 pq」(gcd 里有两个不同质数)
或「质因子的平方 p²」(该质数在 gcd 里出现两次以上)。
"""
return (
[p * q for i, (p, _) in enumerate(factors) for q, _ in factors[i + 1:]] # pq 见证
+ [p * p for p, e in factors if e >= 2] # p² 见证
)
def compress_points(values: list[int], spf: array) -> tuple[NodeList, Witnesses, int]:
"""把同值的点合并,返回 (各组点数, 各组的见证数编号, 见证数个数)。
点权 v 是合数时同一值的点两两有边(gcd = v 是合数),删掉其中一个既不会切分
连通块、也不影响别的点,所以它们合成一个权值 = 点数的节点;点权是质数时同一值
的点两两没边,只能各自留一个权值 1 的节点。度为 1 的见证数只连着唯一一个点,
永远不影响连通性,一并剪掉。两处都只是把图压小,算法完全不变。
"""
degree: IdMap = {} # 见证数 -> 包含它的点(合并后)个数
weights: NodeList = []
grouped: Witnesses = [] # 合并后每个点的见证数列表(未剪枝)
for value, group in Counter(values).items():
ws = witnesses_of(prime_powers(value, spf))
# ws 非空 <=> v 是合数 <=> 同值的 group 个点是一个团,可合并成一个权值 group 的点
weights += [group] if ws else [1] * group
grouped += [ws] if ws else [[] for _ in range(group)]
for d in ws:
degree[d] = degree.get(d, 0) + 1
base = len(weights) # 见证数节点编号排在所有合并点之后
ids: IdMap = {}
kept: Witnesses = []
for ws in grouped:
row: list[int] = []
for d in ws:
if degree[d] < 2: # 只被一个点独占的见证数不影响连通性,剪掉
continue
if d not in ids:
ids[d] = base + len(ids) # 第一次见到就发一个节点编号
row.append(ids[d])
kept.append(row)
return weights, kept, len(ids)
def build_adj(weights: NodeList, wit: Witnesses) -> Adj:
"""把「合并点 + 见证数」二部图展开成双向邻接表。"""
adj: Adj = [[] for _ in range(len(weights) + sum(map(len, wit)))]
for j, row in enumerate(wit):
adj[j] = row # 合并点只连自己的见证数
for d in row:
adj[d].append(j) # 见证数连回它的合并点
return adj
def lowlink(adj: Adj, point_weight: NodeList) -> LowInfo:
"""迭代 Tarjan:返回 (dfn, low, 子树点数, 连通块号, 连通块点数表, 父亲)。
子树点数只统计合并点(见证数不计入),连通块点数表从下标 1 起给连通块编号。
"""
nodes = len(adj)
m = len(point_weight)
disc = [0] * nodes
low = [0] * nodes
par = [NO_PARENT] * nodes
sub = [0] * nodes # 子树里的合并点数
comp = [0] * nodes
comp_total = [0] # comp_total[c] 是连通块 c 的合并点总数
step = [0] * nodes # 每个节点下一条待遍历的邻边位置
timer = 0
for s in range(nodes):
if disc[s]:
continue
cid = len(comp_total)
timer += 1
disc[s] = low[s] = timer
par[s] = NO_PARENT
sub[s] = point_weight[s] if s < m else 0
comp[s] = cid
total = sub[s]
stack = [s]
while stack:
v = stack[-1]
if step[v] < len(adj[v]):
u = adj[v][step[v]]
step[v] += 1
if u == par[v]:
continue # 不回走 DFS 树上的父边
if disc[u] == 0:
timer += 1
disc[u] = low[u] = timer
par[u] = v
sub[u] = point_weight[u] if u < m else 0
comp[u] = cid
total += sub[u]
stack.append(u)
elif disc[u] < low[v]:
low[v] = disc[u] # 回边:low 取 dfn 更小的那个
else:
stack.pop()
p = par[v]
if p != NO_PARENT:
if low[v] < low[p]:
low[p] = low[v]
sub[p] += sub[v]
comp_total.append(total)
return disc, low, sub, comp, comp_total, par
def smallest_after_removal(weights: NodeList, wit: Witnesses) -> int:
"""一组数据的答案:删掉一个点后最大连通块的最小可能值。
对每个合并点 x:权值 >= 2 的组删一个点不会切分连通块,只是该块少一个点;
权值 == 1 的组等于删掉这个节点,要用 low/cut 判定被切出去的最大子树。
"""
adj = build_adj(weights, wit)
disc, low, sub, comp, comp_total, par = lowlink(adj, weights)
m = len(weights)
# 各连通块点数的最大 / 次大 / 最大者个数(并列最大时「其他连通块」仍是最大者)
top1 = top2 = ties = 0
for total in comp_total[1:]:
if total > top1:
top2, top1, ties = top1, total, 1
elif total == top1:
ties += 1
elif total > top2:
top2 = total
best = sum(weights) - 1 # 答案上界:删一个点后至多剩 n-1 个点
for x in range(m):
total = comp_total[comp[x]]
other = top2 if (total == top1 and ties == 1) else top1
if weights[x] > 1:
cur = max(total - 1, other) # 组里少一个点,连通块不被切分
else:
cut_max = 0
rest = total - 1 # 去掉 x 与被切出的各子树后剩下的主体
for u in adj[x]:
is_cut_off = par[u] == x and low[u] >= disc[x] # 这个儿子被 x 切出去了
if is_cut_off:
if sub[u] > cut_max:
cut_max = sub[u]
rest -= sub[u]
cur = max(cut_max, rest, other)
if cur < best:
best = cur
return best
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
T = next(data)
tests = []
max_value = 2
for _ in range(T):
n = next(data)
values = [next(data) for _ in range(n)]
tests.append(values)
max_value = max(max_value, max(values))
spf = build_spf(max_value) # 全题共用一张最小质因子表
out = []
for values in tests:
weights, wit, _ = compress_points(values, spf)
out.append(str(smallest_after_removal(weights, wit)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 20:20
* update_at: 2026-10-07 20:40
*/
// main.cpp:一本通 1736《最大连通块》,删掉一个点使剩余图的最大连通块最小。
//
// 关键观察:gcd(a_u, a_v) 是合数 <=> gcd 的质因数分解里至少有两个质因子(按重数计)
// <=> 存在“见证数” w ∈ { p*q | p<q 为质数 } ∪ { p^2 | p 为质数 }
// 同时整除 a_u 与 a_v。于是把每个出现过的见证数也当成一个点,建成二部图
// (左侧 = 原来的 n 个点,右侧 = 见证数),原点 u 连向它所有的见证数。
// 引理 1:二部图里两个原点的连通性与原图中一样(相邻原点夹着一个公共见证数,
// 反过来原图的每条边都对应一个公共见证数)。
// 引理 2:见证数点永远不会被删掉,所以删掉原点 x 后,原图的连通块 = 二部图删 x 后
// 的连通块(只数原点)。
// 于是只需在二部图上跑一趟 Tarjan(dfn / low / 子树里的原点个数),就能对每个原点 x
// 在 O(deg x) 内算出“删 x 后的最大连通块”,取最小值即答案。
//
// 复杂度:线性筛 O(maxA),每组数据 O(n log maxA) 分解 + O((n + |W|)·36) 建图与 Tarjan。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000; // n 的上限
const int MAXA = 10000000; // a_i 的上限(筛法只开到实际最大值)
const int MAXWIT = 36; // 单点见证数上限:C(8,2)+8 = 36(1e7 内最多 8 个不同质因子)
const int MAXWREL = MAXWIT * MAXN + 10; // “原点 -> 见证数”关系条数上限(见证数个数不超过它)
const int MAXNODE = (MAXWIT + 1) * MAXN + 10; // 二部图点数上限:原点 + 见证数
int spf[MAXA + 1]; // spf[x] = x 的最小质因子,线性筛(x 为质数时即 x 本身)
int wid[MAXA + 1]; // wid[d] = 见证数 d 在当前这组数据内分到的局部编号;配合 baseId 判“本轮是否已分配”
int wrel[MAXWREL]; // 扁平存“原点 i 的见证数”,第 i 个原点的区间由 woff[i] 起
int woff[MAXN + 2]; // 原点的关系区间起点
int wdeg[MAXWREL]; // 每个见证数(局部编号)被多少个原点共享
// 一组数据:点数 + 点权序列。用 struct 聚合,避免下标平行的多个数组。
struct TestCase {
int n; // 这组数据的点数
vector<int> a; // 这组数据的点权 a[0..n-1]
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
// 先把所有数据读进来,才知道最小质因子筛要开到多大
vector<TestCase> tests(T);
int maxA = 2; // 筛法上界 = 所有 a_i 的最大值
for (int t = 0; t < T; t++) {
cin >> tests[t].n;
tests[t].a.resize(tests[t].n);
for (int i = 0; i < tests[t].n; i++) {
cin >> tests[t].a[i];
if (tests[t].a[i] > maxA) maxA = tests[t].a[i];
}
}
// 线性筛最小质因子:分解一个数时每次至少消掉一个质因子
{
vector<int> primes;
primes.reserve(maxA / 10 + 16);
for (int i = 2; i <= maxA; i++) {
if (spf[i] == 0) {
spf[i] = i;
primes.push_back(i);
}
for (size_t j = 0; j < primes.size(); j++) {
ll p = primes[j]; // 声明成 ll,p * i 就按 64 位算,不会溢出
if (p > spf[i] || p * i > maxA) break;
spf[p * i] = p;
}
}
}
int fresh = 0; // 全局单调递增的见证数计数;本组新建的见证数编号是 baseId+1 .. fresh
int pr[16]; // 临时存放一个数的不同质因子
int pe[16]; // 对应的指数
vector<int> ofs; // CSR 的行起始下标,ofs[N] 是总边数(无向边双向各存一条)
vector<int> adj; // CSR 的边表
vector<int> disc, low, par, itp, sz, comp;
vector<int> compTot; // compTot[c] = 连通块 c 里的原点个数
vector<int> stk; // 迭代 DFS 的手写栈
for (int t = 0; t < T; t++) {
int n = tests[t].n;
int baseId = fresh;
// 1) 分解每个 a_i,枚举它的全部见证数,给“本组首次出现”的见证数分配局部编号
woff[0] = 0;
int we = 0;
for (int i = 0; i < n; i++) {
int x = tests[t].a[i];
int k = 0;
while (x > 1) {
int p = spf[x], e = 0;
while (x % p == 0) {
x /= p;
e++;
}
pr[k] = p;
pe[k] = e;
k++;
}
// p*q 型见证:两个不同质数同时整除等号右边的 gcd
for (int j = 0; j < k; j++) {
for (int j2 = j + 1; j2 < k; j2++) {
int d = pr[j] * pr[j2];
if (wid[d] <= baseId) wid[d] = ++fresh;
wrel[we++] = wid[d] - baseId - 1; // 见证数的局部编号
}
// p^2 型见证:某个质数在 gcd 里出现两次以上
if (pe[j] >= 2) {
int d = pr[j] * pr[j];
if (wid[d] <= baseId) wid[d] = ++fresh;
wrel[we++] = wid[d] - baseId - 1;
}
}
woff[i + 1] = we;
}
int W = fresh - baseId; // 本组用到的见证数个数
int N = n + W; // 二部图点数:前 n 个是原点,后面是见证数
// 2) 建二部图的 CSR:先数见证数度数,再算行起始,最后填边表
for (int w = 0; w < W; w++) wdeg[w] = 0;
for (int e = 0; e < we; e++) wdeg[wrel[e]]++;
ofs.assign(N + 1, 0);
for (int v = 0; v < n; v++) ofs[v + 1] = ofs[v] + (woff[v + 1] - woff[v]);
for (int w = 0; w < W; w++) ofs[n + w + 1] = ofs[n + w] + wdeg[w];
adj.assign(ofs[N], 0);
{
vector<int> pos(ofs.begin(), ofs.begin() + N); // 每个顶点的“下一个空位”
for (int i = 0; i < n; i++) {
for (int e = woff[i]; e < woff[i + 1]; e++) {
int w = n + wrel[e];
adj[pos[i]++] = w;
adj[pos[w]++] = i;
}
}
}
// 3) 迭代 Tarjan:dfn / low / 父亲 / 子树里的原点个数 / 连通块原点总数
disc.assign(N, 0);
low.assign(N, 0);
par.assign(N, -1);
itp.assign(N, 0);
sz.assign(N, 0);
comp.assign(N, 0);
compTot.clear();
stk.reserve(N);
int timer = 0;
for (int s = 0; s < N; s++) {
if (disc[s]) continue;
int cid = (int)compTot.size();
int cnt = 0;
disc[s] = low[s] = ++timer;
par[s] = -1;
itp[s] = ofs[s];
sz[s] = (s < n) ? 1 : 0; // 只有原点计入块大小
comp[s] = cid;
if (s < n) cnt++;
stk.clear();
stk.push_back(s);
while (!stk.empty()) {
int v = stk.back();
if (itp[v] < ofs[v + 1]) {
int u = adj[itp[v]++];
if (u == par[v]) continue; // 不走回 DFS 树上父亲的那条边
if (disc[u] == 0) {
disc[u] = low[u] = ++timer;
par[u] = v;
itp[u] = ofs[u];
sz[u] = (u < n) ? 1 : 0;
comp[u] = cid;
if (u < n) cnt++;
stk.push_back(u);
} else if (disc[u] < low[v]) {
low[v] = disc[u]; // 回边:low 取 dfn 更小的那个
}
} else {
stk.pop_back();
int p = par[v];
if (p != -1) {
if (low[v] < low[p]) low[p] = low[v];
sz[p] += sz[v];
}
}
}
compTot.push_back(cnt);
}
// 4) 各连通块原点数的最大 / 次大 / 最大者个数
// (最大值并列时,“其他连通块的最大值”仍然等于最大值,所以必须记个数)
int t1 = 0, t2 = 0, cnt1 = 0;
for (size_t c = 0; c < compTot.size(); c++) {
int v = compTot[c];
if (v > t1) {
t2 = t1;
t1 = v;
cnt1 = 1;
} else if (v == t1) {
cnt1++;
} else if (v > t2) {
t2 = v;
}
}
// 5) 对每个原点 x 算“删 x 后最大连通块”,取最小值
int best = INT_MAX;
for (int x = 0; x < n; x++) {
int cid = comp[x];
int ctot = compTot[cid];
int other = (ctot == t1 && cnt1 == 1) ? t2 : t1; // x 之外其他连通块的最大值
int rest = ctot - 1; // x 所在块去掉 x 与被切出的子树后剩下的主体
int sepMax = 0; // 被 x 切出去的最大子树
for (int e = ofs[x]; e < ofs[x + 1]; e++) {
int u = adj[e];
if (par[u] == x && low[u] >= disc[x]) { // 这个儿子子树被 x 切掉
if (sz[u] > sepMax) sepMax = sz[u];
rest -= sz[u];
}
}
int M = max(sepMax, max(rest, other));
if (M < best) best = M;
}
cout << best << "\n";
}
return 0;
}复杂度
- 时间:线性筛
( );每组数据分解 , 建图与 Tarjan 。 、 、 时总规模约 个原点、 条二部边; 邻接表用 CSR( ofs[]+adj[])而不是指针式链式前向星,实测最坏的一组 (、 、全部点权都是 8 个不同质因子的小乘积,见证数打满上限 36) C++ 跑 0.18 s,仓库给定的 10 个点里最慢的点 9 是 0.14 s(限时 2000 ms)。 - 空间:最小质因子表
字节( int数组,项,约 38 MB) 加上 CSR 邻接表 ; 的满规模数据实测峰值 112 MB, 在 512 MB 限制内。 - Python 侧:核心是
array+ 显式栈的迭代 Tarjan,与 C++ 同阶;因为常数大, 顶格点()有 TLE 风险,属于仓库规范允许的范围,算法没有降级。 作为代价,Python 版本额外做了两处不改算法的图压缩:点权相同且为合数的一批点 合成一个权值等于点数的节点(它们是一个团,删其中一个不切分连通块),以及剪掉 度数只有 1 的见证数节点(它们不影响连通性)。实测仓库 10 个真实点中最慢的点 8 为 3.3 s。
总结
为合数可以"降维"成共享见证数: 是合数 含 或 , 于是"两数互质以外还有更细的差别"变成"两个集合有交",边就在集合之间铺开了。 - 交集关系天然适合二部图:原点—见证数二部图把
条潜在线性化到 条, 并且完全保住了连通性(路径来回翻译都成立)。 - 删点问题不要真的删点:见证数点不会被删,所以只要在原图上做一次 Tarjan,
用
判割点、用子树原点数 算块大小, 就能 地得到每个 的答案。 - "其他连通块"要靠最大 / 次大判重:最大值并列时次大值仍然等于最大值,写代码时 必须带一个"最大者出现次数"才不出错。
- 本题素材源带数据生成脚本
data.py,说明data/是自造的,题面也属于网络重建(与官方页的 时限 / 样例一致),出题意图与原题可能有偏差;素材源的std.cpp已编译并于 10 个点上 与main.cpp逐一比对,结果完全一致,本题解可以放心按它核对。
图示解析
下图画的是二部图转换。左侧方框是原点(点权标在旁边),右侧圆角框是见证数, 一个原点连到它所有权见数;两个原点共享见证数就等价于原图中有边。
flowchart LR
A["a=36"] --- W1["4 = 2²"]
A --- W2["6 = 2·3"]
A --- W3["9 = 3²"]
B["a=20"] --- W4["4 = 2²"]
B --- W5["10 = 2·5"]
对照样例第二组: