最大因子聚簇规模:阈值化相关性图的最大连通分量大小
Largest Factor Cluster Size: Maximum Connected Component on a Thresholded Correlation Graph
开始编码实现 solution(corr: list[list[float]], tau: float) -> int。在下标 0..N-1 上构建无向图,(i, j) 在 i != j 且 abs(corr[i][j]) >= tau 时连边。返回最大块(连通分量)的节点数。若 N == 0 返回 0;若 N == 1 返回 1。
例
solution([[1.0, 0.9, 0.1], [0.9, 1.0, 0.2], [0.1, 0.2, 1.0]], 0.5) 返回 2。顶点 0 与 1 因 |0.9| >= 0.5 形成大小 2 的块;顶点 2 是孤立的(大小 1);最大值为 2。负幅度检查:solution([[1.0, -0.6], [-0.6, 1.0]], 0.5) 返回 2,因为 |-0.6| = 0.6 >= 0.5。空情形 solution([], 0.3) 返回 0;单元素情形 solution([[1.0]], 0.3) 返回 1。
参考解一遍走严格上三角,把耦合送进带路径压缩和按秩合并的并查集,挂一个按根索引的 size[],并在每次合并后用 largest = max(largest, size[new_root]) 更新答案。从每个未访问顶点起跑 BFS / DFS、对访问数取最大值,是等价的另一种走法。Floyd–Warshall 式的闭包扫描是 O(N^3),会超时——只要"分量划分加各分量基数"就够,闭包矩阵是多余工作量。
契约细节:阈值采用闭包含 (>=);负幅度走 abs()(tau = 0.5 下 -0.5 与 +0.5 等价耦合);对角线排除。空 (N == 0) 与单元素 (N == 1) 在 tau 边界检查之前短路(无论 tau 取值,答案都良定);当 N >= 2 时先校验 tau。校验行为:tau 落在 (0, 1) 之外(包括端点)抛 ValueError;矩阵在 1e-9 容差之外不对称抛 ValueError;非方阵形状(某行长度不等于 N)抛 ValueError。对角线条目 corr[i][i] = 1.0 属于输入域约定——由调用方保证,函数不再回头校验对角线(其取值会被直接忽略,因为 i == j 被排除在边扫描之外)。请读清楚:答案是最大块的大小,不是块的数量。全连通图返回 N;全不连通图返回 1;仅一条 2 顶点边加 N - 2 个孤立顶点的图返回 2。
实现细节由 stubs/stub.py 提供。
实践背景
最大块大小是阈值化共动图上风险集中度的单数标量表盘。当一个块吞下相当一部分 universe,分散化叙事就坍缩到一根主导轴上,集中度上限——通常直接写成这个数("任一连通风险块占用资本不得超过 30%")——开始约束。运营上风险线每晚把这条流水线在几个候选阈值上跑一遍,盯住最大块是否跳起来。abs() 规则反映对冲对称性:-0.8 一对与 +0.8 一对一样把两个名字钉在同一根风险轴上。闭区间 >= 与策略文档对截止值的写法一致。
约束条件
- 0 <= N <= 600,其中 N 是 corr 矩阵的边长
- corr 是 N x N 的实数方阵,满足 corr[i][i] = 1.0 与 corr[i][j] = corr[j][i](对称性在 1e-9 容差内校验,超出容差的硬不对称会抛 ValueError)
- tau 必须满足 0.0 < tau < 1.0;落在该开区间之外(包括 0.0 与 1.0)的取值会抛 ValueError
- i != j 且 abs(corr[i][j]) >= tau 时连边(阈值闭包含,对负相关同样有效)
- N == 0 时返回 0、N == 1 时返回 1 在 tau 校验之前短路;N >= 2 时输出为 [1, N] 区间内的正整数,使用精确比对
样例
Case 1 · statement-example: three nodes, largest cluster size 2
输入: [[[1,0.9,0.1],[0.9,1,0.2],[0.1,0.2,1]],0.5]
期望: 2
下标 0 与 1 由 |0.9| >= 0.5 连通形成大小 2 的聚簇;下标 2 是大小 1 的孤立簇;最大值为 2。
Case 2 · visible: negative correlation forms one cluster of size 2
输入: [[[1,-0.6],[-0.6,1]],0.5]
期望: 2
负相关 -0.6 的绝对值 0.6 >= 0.5,两个名字属于同一聚簇,大小为 2。
Case 3 · visible: empty matrix returns 0
输入: [[],0.3]
期望: 0
空 universe,无任何节点,返回 0。
Case 4 · visible: single node returns 1
输入: [[[1]],0.3]
期望: 1
单个孤立名字本身构成一个大小为 1 的平凡聚簇。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: three nodes, largest cluster size 2
输入: [[[1,0.9,0.1],[0.9,1,0.2],[0.1,0.2,1]],0.5]
期望: 2
下标 0 与 1 由 |0.9| >= 0.5 连通形成大小 2 的聚簇;下标 2 是大小 1 的孤立簇;最大值为 2。
Case 2 · visible: negative correlation forms one cluster of size 2
输入: [[[1,-0.6],[-0.6,1]],0.5]
期望: 2
负相关 -0.6 的绝对值 0.6 >= 0.5,两个名字属于同一聚簇,大小为 2。
Case 3 · visible: empty matrix returns 0
输入: [[],0.3]
期望: 0
空 universe,无任何节点,返回 0。
Case 4 · visible: single node returns 1
输入: [[[1]],0.3]
期望: 1
单个孤立名字本身构成一个大小为 1 的平凡聚簇。