最大连通块

GitHub跳转原题关系图返回列表

把 gcd 为合数翻译成共享「见证数 pq / p²」,在原点加见证数的二部图上跑 Tarjan 求割点子树,逐个点算出删点后的最大连通块。

OJ: roj

题目 ID: 1736

难度:提高+/省选-

标签:图论数论Tarjan割点质因数分解连通块python

创建: 2026-10-07 20:59

更新: 2026-10-07 20:59

形式化题目

给定 nn 个点与点权 a1,…,ana_1, \dots, a_n(ai⩾2a_i \geqslant 2),无向图 GG 的边集为

E={ {u,v}  ∣  u≠v, gcd⁡(au,av) 是合数 }.E = \bigl\{\, \{u, v\} \;\bigm|\; u \neq v,\ \gcd(a_u, a_v) \text{ 是合数} \,\bigr\}.

要求恰好删除一个点 xx,使 G−xG - x 中最大连通块的大小最小,输出这个最小值:

ans=min⁡1⩽x⩽n max⁡C 是 G−x 的连通块∣C∣.\text{ans} = \min_{1 \leqslant x \leqslant n} \ \max_{C \text{ 是 } G - x \text{ 的连通块}} |C|.

多组数据,T⩽10T \leqslant 10,n⩽105n \leqslant 10^5,ai⩽107a_i \leqslant 10^7。

以题面第一组样例 a=(8,4,12,18,9)a = (8, 4, 12, 18, 9) 为例,枚举删哪个点时 G−xG - x 的连通块如下 (删掉 xx 后 xx 本身消失,所以剩余块的大小之和是 n−1=4n - 1 = 4):

删除 xx 11 22 33 44 55
axa_x 88 44 1212 1818 99
各连通块大小 44 44 2, 22,\,2 3, 13,\,1 44
最大块 $ M(x) $ 44 44 2\mathbf{2}

删掉 a3=12a_3 = 12 时,剩下的 {8,4,18,9}\{8, 4, 18, 9\} 被拆成 {8,4}\{8, 4\} 与 {18,9}\{18, 9\} 两块, 最大块降到 22(删其他点时都还有一块大小 33 或 44 ),所以第一组答案是 22。 三组样例的答案分别是 2/3/62 / 3 / 6。

正解

思路

第一步:把数论条件换成图论条件。 直接判边需要 O(n2)O(n^2) 次 gcd⁡\gcd,而 gcd⁡\gcd 是合数 这件事可以拆开看。设 d=gcd⁡(au,av)d = \gcd(a_u, a_v),“dd 是合数"等价于"dd 的质因数分解里 带的质因子个数(按重数计)Ω(d)⩾2\Omega(d) \geqslant 2”。Ω(d)⩾2\Omega(d) \geqslant 2 又等价于

  • 存在两个不同的质数 p<qp < q 同时整除 dd,即 pq∣dpq \mid d;
  • 或者存在质数 pp 满足 p2∣dp^2 \mid d。

把这两类数统称为见证数:

W(a)={ pq∣p<q 为质数, pq∣a }∪{ p2∣p 为质数, p2∣a }.W(a) = \{\, pq \mid p < q \text{ 为质数},\ pq \mid a \,\} \cup \{\, p^2 \mid p \text{ 为质数},\ p^2 \mid a \,\}.

于是

gcd⁡(au,av) 是合数  ⟺  W(au)∩W(av)≠∅,\gcd(a_u, a_v) \text{ 是合数} \iff W(a_u) \cap W(a_v) \neq \varnothing,

原图的一条边变成了"两个点共享一个见证数"。

第二步:把共享关系摊成二部图。 建一个二部图 HH:左侧是 nn 个原点(原图的点), 右侧是所有出现过的见证数(每个见证数一个点),原点 uu 与见证数 ww 连边当且仅当 w∣auw \mid a_u。

这个转换的关键性质是:HH 中两个原点的连通性与 GG 中一样。 沿着 HH 中一条只含原点的路径 u1→w1→u2→w2→⋯→uku_1 \to w_1 \to u_2 \to w_2 \to \cdots \to u_k, 相邻两个原点 ui,ui+1u_i, u_{i+1} 之间夹着的 wiw_i 同时属于 W(ui)W(u_i) 与 W(ui+1)W(u_{i+1}), 所以 gcd⁡(aui,aui+1)\gcd(a_{u_i}, a_{u_{i+1}}) 是合数,GG 中确实有边,路径可翻译回 GG; 反过来 GG 的每条边 (u,v)(u,v) 取一个共享见证数,就得到 HH 中长度 2 的通路。 两边方向都成立,所以连通性一致。

第三步:把"删点"也搬过去。 删掉的是原点。注意见证数点永远不会被删掉, 于是 G−xG - x 中的连通块,与 H−xH - x 的各个连通块(只数原点)一一对应: G−xG-x 里两个点连通   ⟺  \iff H−xH-x 里它们连通。问题变成:

在 HH 中删去原点 xx,使剩余部分(只数原点)的最大连通块最小。

第四步:一次 Tarjan 解决所有 xx。 在 HH 上跑一遍 DFS 求出 dfn\mathrm{dfn}、low\mathrm{low}、以及每个节点子树中的原点个数 szsz(见证数点不计入 szsz), 再求出每个连通块的原点总数。对原点 xx 分三种情况:

  1. 根的儿子 cc 满足 low[c]⩾dfn[x]\mathrm{low}[c] \geqslant \mathrm{dfn}[x]:xx 是割点,删除 xx 后 这棵子树与原连通块剩余部分分开,得到一块大小 sz[c]sz[c];
  2. 原连通块去掉 xx 与所有被切出的子树后,剩下的部分大小为 tot(component)−1−∑被切出sz[c]\mathrm{tot}(\text{component}) - 1 - \sum_{\text{被切出}} sz[c];
  3. 其他连通块不受影响,大小不变。

所以

M(x)=max⁡( max⁡被切出sz[c],  tot[comp(x)]−1−∑被切出sz[c],  其他连通块的最大原点数 ),M(x) = \max\Bigl(\ \max_{\text{被切出}} sz[c],\ \ \mathrm{tot}[\mathrm{comp}(x)] - 1 - \textstyle\sum_{\text{被切出}} sz[c],\ \ \text{其他连通块的最大原点数}\ \Bigr),

答案就是 min⁡xM(x)\min_x M(x),其中 M(x)M(x) 就是这里的最大块。 "其他连通块的最大值"用各连通块原点总数的最大 / 次大值 O(1)O(1) 得到, 注意最大值并列时次大值要取最大本身(下面代码里的 ties 计数就是干这个的)。

复杂度来源。 一个 a⩽107a \leqslant 10^7 的数最多有 8 个不同的质因子(2⋅3⋅5⋅7⋅11⋅13⋅17⋅19=9 699 6902\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 = 9\,699\,690), 所以 ∣W(a)∣⩽(82)+8=36|W(a)| \leqslant \binom{8}{2} + 8 = 36。HH 的点数是 O(n)O(n)、边数是 O(36n)O(36n), 分解用最小质因子筛做到单个数 O(log⁡a)O(\log a)。总时间

O(maxAlog⁡log⁡maxA+∑t(ntlog⁡\maxA+36nt)),O\bigl(\text{maxA} \log\log \text{maxA} + \sum_t (n_t \log \maxA + 36 n_t)\bigr),

空间 O(maxA+36n)O(\text{maxA} + 36n)。

代码

Python 版(同一算法;为了让 CPython 能跑动顶格数据,额外做了两处不改算法的图压缩: 点权相同且为合数的一批点合成一个权值等于点数的节点,以及剪掉度数只有 1 的见证数节点):

python
#!/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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:线性筛 O(\maxA)O(\maxA)(\maxA=max⁡ai\maxA = \max a_i);每组数据分解 O(nlog⁡\maxA)O(n \log \maxA), 建图与 Tarjan O((n+∣W∣)⋅36)=O(36n)O\bigl((n + |W|) \cdot 36\bigr) = O(36n)。T⩽10T \leqslant 10、n⩽105n \leqslant 10^5、 ai⩽107a_i \leqslant 10^7 时总规模约 10610^6 个原点、3.6×1063.6 \times 10^6 条二部边; 邻接表用 CSR(ofs[] + adj[])而不是指针式链式前向星,实测最坏的一组 (T=10T = 10、n=105n = 10^5、全部点权都是 8 个不同质因子的小乘积,见证数打满上限 36) C++ 跑 0.18 s,仓库给定的 10 个点里最慢的点 9 是 0.14 s(限时 2000 ms)。
  • 空间:最小质因子表 4×1074 \times 10^7 字节(int 数组,107+110^7 + 1 项,约 38 MB) 加上 CSR 邻接表 O(36n)O(36n);max⁡ai=107\max a_i = 10^7 的满规模数据实测峰值 112 MB, 在 512 MB 限制内。
  • Python 侧:核心是 array + 显式栈的迭代 Tarjan,与 C++ 同阶;因为常数大, 顶格点(T×n=106T \times n = 10^6)有 TLE 风险,属于仓库规范允许的范围,算法没有降级。 作为代价,Python 版本额外做了两处不改算法的图压缩:点权相同且为合数的一批点 合成一个权值等于点数的节点(它们是一个团,删其中一个不切分连通块),以及剪掉 度数只有 1 的见证数节点(它们不影响连通性)。实测仓库 10 个真实点中最慢的点 8 为 3.3 s。

总结

  • gcd⁡\gcd 为合数可以"降维"成共享见证数:dd 是合数   ⟺  \iff dd 含 pqpq 或 p2p^2, 于是"两数互质以外还有更细的差别"变成"两个集合有交",边就在集合之间铺开了。
  • 交集关系天然适合二部图:原点—见证数二部图把 O(n2)O(n^2) 条潜在线性化到 O(36n)O(36n) 条, 并且完全保住了连通性(路径来回翻译都成立)。
  • 删点问题不要真的删点:见证数点不会被删,所以只要在原图上做一次 Tarjan, 用 low[c]⩾dfn[x]\mathrm{low}[c] \geqslant \mathrm{dfn}[x] 判割点、用子树原点数 sz[c]sz[c] 算块大小, 就能 O(1)O(1) 地得到每个 xx 的答案。
  • "其他连通块"要靠最大 / 次大判重:最大值并列时次大值仍然等于最大值,写代码时 必须带一个"最大者出现次数"才不出错。
  • 本题素材源带数据生成脚本 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"]

对照样例第二组:3636 与 2020 的 gcd⁡\gcd 是 4=224 = 2^2,是合数,两者通过见证数 44 连通; 3636 与 4545 的 gcd⁡\gcd 是 9=329 = 3^2,也是合数,它们通过见证数 99 连通; 而 3636 与 231=3⋅7⋅11231 = 3 \cdot 7 \cdot 11 的 gcd⁡\gcd 是 33(质数), 231231 的见证数是 {21,33,77}\{21,33,77\}、3636 的见证数是 {4,6,9}\{4,6,9\},交集为空, 在原图里就不相邻。把三组样例逐点铺开后可以看到, 题目给的三个答案 2/3/62 / 3 / 6 都对应"删掉某个点后最大块被切小"的位置, 这正是 low\mathrm{low} 条件筛出来的那些点;读代码时把「被切出去的最大子树」与 「剩下的主体」两项对应上,是理解这段 Tarjan 的关键。