L2-005 集合相似度

#include <iostream> // 输入输出库
#include <unordered_set> // 使用哈希表存储集合
#include <iomanip> // 用于格式化输出
#include <vector> // 用于存储集合
using namespace std; // 使用标准命名空间

int main() {
    int N; // 集合的个数
    cin >> N; // 读取集合的个数

    // 存储所有集合
    vector<unordered_set<int>> sets(N + 1); // 集合编号从1到N

    // 读取每个集合
    for (int i = 1; i <= N; i++) {
        int M; // 集合中元素的数量
        cin >> M; // 读取集合中元素的数量
        for (int j = 0; j < M; j++) {
            int element; // 集合中的元素
            cin >> element; // 读取元素
            sets[i].insert(element); // 将元素插入集合，unordered_set自动去重
        }
    }

    int K; // 需要计算相似度的集合对数
    cin >> K; // 读取集合对数

    // 计算每对集合的相似度
    for (int i = 0; i < K; i++) {
        int set1, set2; // 需要计算相似度的两个集合的编号
        cin >> set1 >> set2; // 读取集合编号

        // 计算交集大小
        int Nc = 0;
        // 遍历较小的集合
        const unordered_set<int>& smallerSet = (sets[set1].size() < sets[set2].size()) ? sets[set1] : sets[set2];
        const unordered_set<int>& largerSet = (sets[set1].size() < sets[set2].size()) ? sets[set2] : sets[set1];
        for (int element : smallerSet) {
            if (largerSet.count(element)) {
                Nc++; // 如果在，则交集大小加1
            }
        }

        // 计算并集大小
        int Nt = sets[set1].size() + sets[set2].size() - Nc;

        // 计算相似度
        double similarity = (Nc == 0) ? 0.0 : (double)Nc / Nt * 100;

        // 输出结果，保留两位小数
        cout << fixed << setprecision(2) << similarity << "%" << endl;
    }

    return 0; // 程序正常结束
}

for (int element : smallerSet) 是 C++11 引入的范围 for 循环（Range-based for loop），用于遍历容器（如 unordered_set）中的所有元素.

vector<unordered_set<int>> sets(N + 1);：

使用 vector 存储所有集合，每个集合是一个 unordered_set<int>。

unordered_set 是基于哈希表的集合，插入和查找的时间复杂度为 O(1)。

集合编号从1到N，因此 vector 的大小为 N + 1。