ZOOM 2023校招 第3题(C++并查集)

题目描述

请你完成设计一个股票推荐系统，该系统会自动根据注册用户的关注情况进行推荐。
例如，对于一个同时关注了 $Zoom$ 和 $Warmart$ 的人而言，推荐算法会根据他的信息认为，关注了 $Zoom$ 的人，可能对 $Warmart$ 也感兴趣，反之亦然，关注了 $Warmart$ 的人，可能对 $Zoom$ 也感兴趣。
因此，对于另一个关注了 $Warmart$、没关注 $Zoom$ 的人来说，该系统就会推荐他关注 $Zoom$ 。
请注意，该系统会计算连锁的信息，例如假设在刚刚的前提（存在那个同时关注 $Warmart$ 和 $Zoom$ ）下，存在一个同时关注 $Zoom$ 和 $Apple$ 的人，那么对于另一个只关注了 $Warmart$ 的人，该系统会同时推荐他 $Zoom$ 和 $Apple$ 。
现在给出一些人的注册信息和一些询问，你需要回答每次询问时，推荐系统会推荐给那个人多少只他还没关注的股票？

输入描述

第一行输入一个正整数q，代表操作次数。
接下来输入一次操作。
共有两种操作：

1. 注册——格式为：
   第一行输入 1 name n，代表有一个名字为name的人注册了该系统，他关 注了 $n$ 只股票。
   第二行输入几个仅包含英文字母的字符串 $str$，代表这个人关注的股票名字。
   保证不会重复注册，这几个字符串互不相同。
2. 查询——格式为：
   仅有一行，输入2 name，代表询问该推荐系统会给这个人推荐多少只股票。
   $1\le q\le 10000$
   $1\le n\le 5$
   所有字符串均只包含英文字母，且长度不超过 10。
   保证至少有 1 次询问。
   输出描述：
   对于每次询问：
   若查询的人不存在，则输出"error"
   否则输出一个整数，代表该系统查询的推荐数量。

示例

输入

5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple Microsoft
2 Bob
1
2
3
4
5
6
7
8

输出

error
0
1
1
2
3

说明

第一次询问时，系统内还没有名字为Bob的用户，输出error。
第二次询问时，系统不会给Alice推荐任何股票，输出0。
第三次询问时，由于Alice和Bob都关注了Apple，所以系统会给Bob推荐他还没关注的Zoom。

#include 
#include 
#include 
#include 
#include 

using namespace std;

unordered_map<string, string> recSys; // recommendation system 推荐系统

string search(string s) { // 并查集
    // 通常的并查集用的是int数组
    // 这里用string to string
    if (recSys[s] != s)
        recSys[s] = search(recSys[s]);
    return recSys[s];
}

int main() {
    unordered_map<string, vector<string>> users; // 存储用户投资的股票列表
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int mode;
        cin >> mode;
        string name;
        cin >> name;
        if (mode == 1) { // 存数据
            int stock_num; // 此人投资的股票数量
            cin >> stock_num;
            vector<string> stocks(stock_num);
            int existed = 0; // 用于记录 此人 投资的股票中 哪个 是已经在推荐系统中的
            // 默认为 0 号股票
            for (int j = 0; j < stock_num; j++) {
                cin >> stocks[j];
                if (!recSys.count(stocks[j])) // 若第一次出现该股票
                    recSys[stocks[j]] = stocks[j];  // 加入推荐系统
                else
                    existed = j; // 否则用 existed 记录, 任意一个已存在的都行
            }

            users[name] = stocks; 
            string father = search(stocks[existed]); // 选定一个共同的父节点

            for (int j = 0; j < stock_num; j++) {
                recSys[search(stocks[j])] = father; // 以 existed 的那一个为准, 加入推荐系统
                // 这样的结果能保证此人的股票, 都是一个父节点, 彼此都联系在一起
                // 不能用 recSys[stocks[j]] = father
                // 因为这样达不到"牵一发而动全身"的效果
                // 我们要让与stocks[j]有关的 "所有节点" 的最终 father 都一样
                // 实际代码中, 让stocks[j] "原本的"father 指向我们的 "新"father就行了
            }
        } else { // 查找数据
            if (!users.count(name)) {
                cout << "error" << endl; // 查无此人
            } else {
                int ans = 0; // 查询结果

                string same_father = search(users[name][0]); 
                // 都是一个father选谁都一样, 而且投资股票数量肯定大于等于 1, 直接选第一个就行了

                for (auto item: recSys) { // 遍历推荐系统
                    // first就是键值对中的'键', second就是键值对中的'值'
                    if (item.second == same_father && find(users[name].begin(), users[name].end(), item.first) == users[name].end())
                    // 找到
                    // 1. 与此人已投资的股票"有关联"的股票 (同一个father)
                    // 2. 此人"没有"投资的股票 (失散的兄弟姐妹)
                    // 1 和 2 的交集就是 if 中对应的条件
                        ans++;
                }
                cout << ans << endl;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

补充

对于第46行代码的解释：

假设目前推荐系统的并查集为如下状态:

此时，有一个人关注了2个股票， 分别为D 和 B
此时 existed = 1 ——>father = search[“B”] = A
以下是不同代码执行后的区别：

但是！这么做一定会超时

我们不能每次查询推荐数，都遍历并查集吧？题目要求的是推荐数量，那我们是不是能记录并查集中某一个组的总数，查询某人的推荐数量时，直接 “当前总数 - 用户已关注数量” 就是我们要的答案。

旧的注释基本删了，请查看新的注释：

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

unordered_map<string, string> recSys;

unordered_map<string, int> each_group_num;  
// 记录自己有几个小弟(指向自己)
// 如果是最终father, 那这个值就代表整个组的成员数量(包括father自己)

string search(string s) {
    if (recSys[s] != s)
        recSys[s] = search(recSys[s]);
    return recSys[s];
}

int main() {
    unordered_map<string, pair<string, int>> users; // 用户所在组号 and 已经关注的股票数量
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int mode;
        cin >> mode;
        string name;
        cin >> name;
        if (mode == 1) {
            int stock_num;
            cin >> stock_num;
            vector<string> stocks(stock_num);
            int existed = 0; 
            for (int j = 0; j < stock_num; j++) {
                cin >> stocks[j];
                if (!recSys.count(stocks[j])) { // 若第一次出现该股票
                    recSys[stocks[j]] = stocks[j];  
                    each_group_num[stocks[j]] = 1; // 组数初值为 1, 只包含自己
                }
                else 
                    existed = j;
            }
 
            string new_father = search(stocks[existed]); 

            users[name] = make_pair(new_father, stock_num); // 记录数据
            // 注意: 每个组的father随时可能改变!!!
            for (int j = 0; j < stock_num; j++) {
                string old_father = search(stocks[j]); 
                if (old_father != new_father) { 
                	recSys[old_father] = new_father;
                	// 如果与指定new_father不在同一组, 不论新旧, 合并
                     
                    each_group_num[new_father] += each_group_num[old_father];
                    // 不能简单的++, 因为可能是两个大组的合并
                }
            }
        } else {
            if (!users.count(name)) {
                cout << "error" << endl;
            } else {
                int ans;

                string father = search(users[name].first); 
                // 重新查一遍father(所在组)

                ans = each_group_num[father] - users[name].second;
                // 推荐数量 = 用户所在组的总数 - 用户已经关注的股票数量

                users[name] = make_pair(father, users[name].second); 
                // father(所在组)可能有改变, 更新一下数据

                cout << ans << endl;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80