并查集解题思路：CodeFancy 账号使用者最小数量

问题描述

想象学竞赛网站 CodeFancy 举办了 m 场比赛。你在 CodeFancy 上关注了 n 个账号，编号为 1∼n。你知道这 n 个账号分别参加了 m 场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况，你想知道这 n 个账号的使用者最少共有多少人。

具体地，账号和使用者的关系由两条规则限定：

一个人在一场比赛中至多使用一个账号。
一个账号的使用者只有恰好一个人。

输入格式

第一行两个正整数 n,m。

接下来 m 行，每行先输入一个正整数 k，表示参加这场比赛的账号数量；接下来输入 k 个正整数，表示参加这场比赛的账号编号。

输出格式

一行一个非负整数，表示最少的人数。

样例

样例 1 输入

样例 1 输出

样例 1 解释

一种合法的方案是，四个人使用的账号集合分别为：{1,3},{2},{4},{5}。

可以证明，不存在人数更少的合法方案。

解题思路

对于这道题目的解题思路，我们可以使用并查集（Disjoint Set）来解决。

首先，我们创建一个大小为 n 的并查集，每个元素初始时都是独立的根节点。然后，我们遍历每场比赛，将参加该比赛的账号进行合并操作。

具体步骤如下：

初始化并查集，每个账号编号对应一个独立的集合，即根节点为自身。
遍历每场比赛，对于每个比赛中的账号集合，将其中的账号进行合并操作。
遍历并查集，统计根节点的个数，即为使用者的最少人数。

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

class DisjointSet {
public:
    vector<int> parent;

    DisjointSet(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

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

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    DisjointSet dsu(n);

    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        if (k > 0) {
            int prevAccount;
            cin >> prevAccount;
            for (int j = 1; j < k; j++) {
                int account;
                cin >> account;
                dsu.unite(prevAccount, account);
            }
        }
    }

    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == i) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

希望这个思路能够帮助你解决问题！如果你有任何问题，请随时提问。