问题描述

农场共有 N (2 ≤ N ≤ 10,000) 头奶牛，编号从 1 到 N。这些奶牛共掌握 M (1 ≤ M ≤ 30,000) 种语言，编号为 1 到 M。对于第 i 头奶牛，它会 K_i (1 ≤ K_i ≤ M) 种语言，记为 L_{i1}, L_{i2}, ..., L_{iK_i}。所有奶牛掌握的的语言总数不超过 100,000。

如果两头奶牛共同掌握至少一种语言，它们可以直接交流。然而，即使没有共同语言，奶牛们也可以通过其他奶牛进行翻译间接交流。具体来说奶牛 A 和 B 能够对话，当且仅当存在一个奶牛序列 T_1, T_2, ..., T_k，满足 A 和 T_1 掌握某一共同语言，T_1 和 T_2 掌握某一共同语言，……，T_k 和 B 掌握某一共同语言。

农场主希望所有奶牛之间都能够相互通信。他可以购买书籍来教授奶牛任何语言。作为一位节俭的农场主，他希望购买尽可能少数量的书籍，使得所有奶牛能够互相交流。请计算最少需要购买的书籍数量。

输入格式

第一行包含两个整数 N 和 M，用空格分隔。接下来 N 行，第 i+1 行描述第 i 头奶牛会说的语言：首先是一个整数 K_i，随后是 K_i 个整数 L_{i1}, L_{i2}, ..., L_{iK_i}。

输出格式

输出一个整数，表示农场主最少需要购买的书籍数量。

样例输入

3 3
2 3 2
1 2
1 1

样例输出

1

样例解释

只需要给第三头奶牛购买第二种语言（即语言2），即可使所有奶牛相互通信。

解题思路

本题本质上是求连通块的数量。我们将每头奶牛和每种语言都视为图中的节点，奶牛与其掌握的语言之间建立连接边。使用并查集（Union-Find）数据结构来处理这些连通关系。

具体做法如下：

1. 建立并查集，节点编号 1~N 表示 N 头奶牛，N+1~N+M 表示 M 种语言
2. 对于每头奶牛 i 和它掌握的语言 y，将节点 i 与节点 y+N 合并到同一个集合中
3. 合并完成后，统计有多少个不同的连通块包含奶牛节点
4. 答案为连通块数量减 1，这是因为每次购买一种语言可以连接两个原本分离的连通块

参考实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 40005;
int parent[MAXN];
int cowCount[MAXN];
int result;

int findRoot(int x) {
    if (parent[x] == x) return x;
    return parent[x] = findRoot(parent[x]);
}

void uniteSets(int a, int b) {
    int ra = findRoot(a);
    int rb = findRoot(b);
    if (ra != rb) {
        parent[rb] = ra;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    // 初始化并查集
    for (int i = 1; i <= n + m; i++) {
        parent[i] = i;
    }
    
    // 读取每头奶牛掌握的语言并合并集合
    for (int i = 1; i <= n; i++) {
        int langNum;
        cin >> langNum;
        for (int j = 0; j < langNum; j++) {
            int lang;
            cin >> lang;
            uniteSets(i, lang + n);
        }
    }
    
    // 统计有多少个包含奶牛的连通块
    for (int i = 1; i <= n; i++) {
        int root = findRoot(i);
        if (cowCount[root] == 0) {
            result++;
        }
        cowCount[root]++;
    }
    
    // 输出最少需要购买的语言数量
    cout << (result - 1) << "\n";
    return 0;
}

该算法的时间复杂度为 O(N + K × α(N+M))，其中 K 为所有奶牛掌握的语言总数（≤ 100,000），α 为反阿克曼函数，可以认为是常数。空间复杂度为 O(N + M)。