解题思路

本题要求对告警信息进行语义聚类，核心是基于余弦相似度的连通分量问题。题目的关键在于理解弱传递聚类规则：如果告警A与B相似，B与C相似，即使A与C不相似，它们也应属于同一聚类。这实际上是一个典型的并查集问题。

首先需要处理输入数据的合法性验证。输入为空或向量维度不一致时直接返回0。对于合法输入，我们需要计算所有告警对之间的余弦相似度。余弦相似度的计算公式为：

cos(A,B) = (A·B) / (|A| × |B|)

其中A·B表示向量点积，|A|和|B|表示向量的欧几里得范数。当余弦相似度大于等于0.95时，认为两条告警语义相似，需要将它们归入同一聚类。

为了高效地处理聚类合并操作，我们采用并查集数据结构。并查集支持两个核心操作：查找元素所属集合的根节点，以及合并两个集合。通过路径压缩优化，可以使查找操作接近常数时间复杂度。

算法流程如下：首先初始化并查集，每个告警独立成一个集合。然后遍历所有告警对，计算它们的余弦相似度，如果相似度达到阈值则合并两个集合。最后统计每个集合的大小，返回最大的集合大小即为答案。

复杂度分析

时间复杂度：O(n²·d + n²·α(n))，其中n是告警数量，d是向量维度，α是反阿克曼函数（可视为常数）。计算所有告警对的余弦相似度需要O(n²·d)时间，每次相似度计算涉及向量点积和范数计算均为O(d)。并查集的查找和合并操作经过路径压缩优化后均摊时间复杂度为O(α(n))，总共需要O(n²)次操作。

空间复杂度：O(n)，主要用于存储并查集的父节点数组以及统计聚类大小的哈希表。输入数据的存储空间为O(n·d)，但这是必须的输入开销。

代码实现

Python

import sys
import math
from collections import Counter

def solve(alerts):
    # 处理空输入
    if not alerts:
        return 0
    
    n = len(alerts)
    if n == 0:
        return 0
    
    # 检查向量维度一致性
    dim = len(alerts[0][1])
    for i in range(n):
        if len(alerts[i][1]) != dim:
            return 0
    
    # 初始化并查集
    parent = list(range(n))
    
    def find(x):
        # 路径压缩
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        # 合并两个集合
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    
    def cosine_similarity(v1, v2):
        # 计算余弦相似度
        dot_product = sum(a * b for a, b in zip(v1, v2))
        norm1 = math.sqrt(sum(a * a for a in v1))
        norm2 = math.sqrt(sum(b * b for b in v2))
        if norm1 == 0 or norm2 == 0:
            return 0
        return dot_product / (norm1 * norm2)
    
    # 遍历所有告警对，合并相似告警
    for i in range(n):
        for j in range(i + 1, n):
            sim = cosine_similarity(alerts[i][1], alerts[j][1])
            if sim >= 0.95:
                union(i, j)
    
    # 统计每个聚类的大小
    clusters = Counter(find(i) for i in range(n))
    
    # 返回最大聚类大小
    return max(clusters.values())

def main():
    alerts = []
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        parts = line.split()
        alert_id = parts[0]
        embedding = [float(x) for x in parts[1:]]
        alerts.append((alert_id, embedding))
    
    result = solve(alerts)
    print(result)

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    static class UnionFind {
        int[] parent;
        
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        int find(int x) {
            // 路径压缩
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        void union(int x, int y) {
            // 合并两个集合
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
            }
        }
    }
    
    static double cosineSimilarity(double[] v1, double[] v2) {
        // 计算余弦相似度
        double dotProduct = 0;
        double norm1 = 0;
        double norm2 = 0;
        
        for (int i = 0; i < v1.length; i++) {
            dotProduct += v1[i] * v2[i];
            norm1 += v1[i] * v1[i];
            norm2 += v2[i] * v2[i];
        }
        
        norm1 = Math.sqrt(norm1);
        norm2 = Math.sqrt(norm2);
        
        if (norm1 == 0 || norm2 == 0) {
            return 0;
        }
        
        return dotProduct / (norm1 * norm2);
    }
    
    static int solve(List<double[]> embeddings) {
        int n = embeddings.size();
        
        if (n == 0) {
            return 0;
        }
        
        // 检查向量维度一致性
        int dim = embeddings.get(0).length;
        for (int i = 1; i < n; i++) {
            if (embeddings.get(i).length != dim) {
                return 0;
            }
        }
        
        UnionFind uf = new UnionFind(n);
        
        // 遍历所有告警对，合并相似告警
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double sim = cosineSimilarity(embeddings.get(i), embeddings.get(j));
                if (sim >= 0.95) {
                    uf.union(i, j);
                }
            }
        }
        
        // 统计每个聚类的大小
        Map<Integer, Integer> clusterSize = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            clusterSize.put(root, clusterSize.getOrDefault(root, 0) + 1);
        }
        
        // 返回最大聚类大小
        int maxSize = 0;
        for (int size : clusterSize.values()) {
            maxSize = Math.max(maxSize, size);
        }
        
        return maxSize;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<double[]> embeddings = new ArrayList<>();
        
        while (sc.hasNextLine()) {
            String line = sc.nextLine().trim();
            if (line.isEmpty()) {
                continue;
            }
            
            String[] parts = line.split("\\s+");
            double[] embedding = new double[parts.length - 1];
            
            for (int i = 1; i < parts.length; i++) {
                embedding[i - 1] = Double.parseDouble(parts[i]);
            }
            
            embeddings.add(embedding);
        }
        
        int result = solve(embeddings);
        System.out.println(result);
        
        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;

class UnionFind {
public:
    vector<int> parent;
    
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unionSet(int x, int y) {
        // 合并两个集合
        int px = find(x);
        int py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
};

double cosineSimilarity(const vector<double>& v1, const vector<double>& v2) {
    // 计算余弦相似度
    double dotProduct = 0;
    double norm1 = 0;
    double norm2 = 0;
    
    for (size_t i = 0; i < v1.size(); i++) {
        dotProduct += v1[i] * v2[i];
        norm1 += v1[i] * v1[i];
        norm2 += v2[i] * v2[i];
    }
    
    norm1 = sqrt(norm1);
    norm2 = sqrt(norm2);
    
    if (norm1 == 0 || norm2 == 0) {
        return 0;
    }
    
    return dotProduct / (norm1 * norm2);
}

int solve(vector<vector<double>>& embeddings) {
    int n = embeddings.size();
    
    if (n == 0) {
        return 0;
    }
    
    // 检查向量维度一致性
    int dim = embeddings[0].size();
    for (int i = 1; i < n; i++) {
        if ((int)embeddings[i].size() != dim) {
            return 0;
        }
    }
    
    UnionFind uf(n);
    
    // 遍历所有告警对，合并相似告警
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double sim = cosineSimilarity(embeddings[i], embeddings[j]);
            if (sim >= 0.95) {
                uf.unionSet(i, j);
            }
        }
    }
    
    // 统计每个聚类的大小
    map<int, int> clusterSize;
    for (int i = 0; i < n; i++) {
        int root = uf.find(i);
        clusterSize[root]++;
    }
    
    // 返回最大聚类大小
    int maxSize = 0;
    for (auto& p : clusterSize) {
        maxSize = max(maxSize, p.second);
    }
    
    return maxSize;
}

int main() {
    vector<vector<double>> embeddings;
    string line;
    
    while (getline(cin, line)) {
        if (line.empty()) {
            continue;
        }
        
        stringstream ss(line);
        string alertId;
        ss >> alertId;
        
        vector<double> embedding;
        double val;
        while (ss >> val) {
            embedding.push_back(val);
        }
        
        embeddings.push_back(embedding);
    }
    
    int result = solve(embeddings);
    cout << result << endl;
    
    return 0;
}

题目内容

【背景信息】在现代运维体系中，大量告警可能指向同一故障根源（如 “服务器 CPU 利用率过高” 和 “应用响应超时” 可能由同一硬件资源不足导致）。若能将语义相似的告警归为一类，不仅可以减少重复信息的干扰，还能帮助运维人员快速定位故障核心，缩短故障修复时间。

行业内普遍采用自然语言处理（NLP）技术对告警文本进行语义理解，采用基于预训练语言模型（如 BERT、sBERT 等）的语义向量（embedding）转化技术：通过模型处理，每条告警文本被转化为一个高维数值向量，向量的数学特征能够准确反映告警的语义信息，使得两条描述相同故障的告警（即使措辞略有差异），其对应的向量在空间中的距离会非常近；而语义无关的告警，向量距离则较远。

【任务目标】通过语义向量（embedding）对给定的告警信息进行聚类：每条告警包含唯一的 ID 和对应的向量 embedding，要求将余弦相似度≥0.95 的告警归为同一个聚类，并返回数量最大的聚类的告警数量

【规则要求】

聚类判定标准：

1）相似度阈值：当两条告警的余弦相似度 ≥ 0.95 时，判定为语义相似。

2）弱传递聚类（连通图聚类）规则：初始状态：每条告警单独构成一个类别。归入规则：若告警 X 与某类别 C 中的任意一条告警 的余弦相似度 ≥ 0.95，则将 X 归入类别 C。

合并规则：若告警 X 同时满足归入多个类别的条件（即与多个类别中的告警均相似），则这些类别需合并为一个新类别，X 归入该新类别。

传递性保证：聚类过程需确保所有满足相似条件的告警最终被合并到同一类别中。例如：若 A 与 B 相似（余弦相似度 ≥ 0.95），且 B 与 C 相似（余弦相似度 ≥ 0.95），则 A、B、C 必须属于同一类别（即使 A 与 C 的相似度可能 < 0.95）。

输入描述

每一行为一个告警信息，其中第一个字段是告警 ID，后面的字段是告警的嵌入向量。告警信息的总行数不会超过 1000 条。（请注意，测试集中可能包含如样例 2 所示的那种异常情况）

输出描述

找到包含告警数量最多的聚类，输出该聚类的告警数量。若所有告警均无法聚类（即每个类别仅包含 1 条告警），则返回 1；若输入为空列表（无任何告警），或者输入告警信息的向量维度不一致（即不同告警的 embedding 长度不同），则返回 0。

样例1

输入

1 1.0 0.0 0.0  
2 0.99 0.01 0.0  
3 0.0 1.0 0.0  
4 0.0 1.0 0.01  
5 0.1 0.0 0.0 

输出

3

说明

每一行输入的第一个字段是告警 id，后面的字段是告警的嵌入向量，根据余弦相似度≥0.95 的规则，我们得到以下聚类关系：

• 告警 1、2、5 构成一个聚类；

• 告警 3、4 构成一个聚类；

  所有聚类的大小分别为 3、2。其中数量最大的为 3，因此输出为 3。

样例2

输入

1 1.0 0.0 0.0  
2 0.99 0.01 0.0 0.98  
3 0.0 1.0 0.0

输出

0

说明

第 2 个告警的嵌入向量维度与其他告警不一致，属于异常情况，返回 0

样例3

输入

1 0.878434 -0.068245 -0.46237 0.099552  
2 0.33961 -0.083281 -0.348141 0.869786  
3 0.326485 -0.071012 -0.353166 0.873865  
4 0.330106 -0.085155 -0.338106 0.87719  
5 0.340185 -0.066865 -0.339054 0.874554  
6 0.482266 -0.483077 0.539977 -0.492423  
7 0.491966 -0.485237 0.526674 -0.495104  
8 0.48426 -0.477249 0.531019 -0.505711  
9 -0.669925 -0.330461 0.409454 -0.523778  
10 -0.668543 -0.331692 0.403806 -0.529123

输出

4

说明

每一行输入的第一个字段是告警 id，后面的字段是告警的嵌入向量，根据余弦相似度≥0.95 的规则，我们得到以下聚类关系：

• 告警 2、3、4、5 构成一个聚类；

• 告警 6、7、8 构成一个聚类；

• 告警 9、10 构成一个聚类；

• 告警 1 独立成一个聚类；

  综上所述，所有聚类的大小分别为 4、3、2、1。其中数量最大的为 4，因此输出为 4。