题目描述
你有一个通讯录，每个联系人包含姓名和手机号，一个联系人可能有多个手机号。如果两个联系人拥有相同的手机号，我们认为他们是同一个人。任务是整理通讯录，将具有相同手机号的联系人合并为一个联系人，并返回合并后的通讯录列表。如果合并时发现联系人姓名不同，以字典序小的为姓名。
输入描述
- 第一行：一个整数
num，表示通讯录的记录数量（1 <= num <= 1000）。 - 接下来
num行：每行表示一条联系人记录，包含姓名和若干电话号码（电话号码个数不超过10，长度在1到10之间）。姓名由英文字母大小写组成，长度在1到10之间。
输出描述
整理后的通讯录列表，其中具有相同手机号的联系人合并为一个联系人。输出联系人姓名和手机号码列表按ASCII码升序排序。
用例输入
4
kaka 10000000000 10000000001
tata 10000000020
kaka 10000000000 10000000002
tata 10000000010
kaka 10000000000 10000000001 10000000002
tata 10000000010
tata 10000000020
第一个kaka和第二个kaka有相同的手机号10000000000，因此他们被视为同一个人。合并后的手机号按ASCII码升序排序。
3
kaka 10000000000 10000000001
kaka 10000000001 10000000002
kaka 10000000002 10000000003
kaka 10000000000 10000000001 10000000002 10000000003
第一个kaka和第二个kaka有相同的手机号10000000001，第二个kaka和第三个kaka有相同的手机号10000000002，因此他们被视为同一个人。合并后的手机号按ASCII码升序排序。
解题思路
-
问题建模：
- 使用并查集来合并具有相同手机号的联系人。
- 使用哈希表记录每个手机号对应的联系人索引。
- 使用集合去重并排序手机号。
-
并查集：
- 对于每个联系人的手机号，如果该手机号已经出现过，则将当前联系人与之前出现的联系人合并。
- 使用路径压缩优化并查集。
-
合并联系人：
- 对于每个联系人，找到其根节点（即合并后的代表）。
- 合并手机号，去重并排序。
- 如果姓名不同，选择字典序小的姓名。
-
输出结果：
- 按姓名和手机号的ASCII码升序排序，输出合并后的通讯录。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
#include<iomanip>
#include<cstdint>
using namespace std;// 并查集
vector<int> f(10005);
int find(int x) {if (f[x] == x) return x;else return f[x] = find(f[x]);
}
void un(int x, int y) {int fx = find(x);f[fx] = y;
}int main() {ios::sync_with_stdio(false); // 关闭与 C 的同步cin.tie(nullptr); // 解除 cin 与 cout 的绑定int n;cin >> n;cin.ignore();vector<string> name(n);vector<vector<string>> phone(n);map<string, int> memo; // 记录手机号对应的联系人索引for (int i = 0; i < n; i++) {f[i] = i; // 初始化并查集string input, temp;getline(cin, input);istringstream is(input);is >> name[i];while (is >> temp) {if (memo.count(temp)) { // 如果手机号已经出现过un(memo[temp], i); // 合并两个联系人}memo[temp] = i; // 更新手机号对应的联系人索引phone[i].push_back(temp); // 记录当前联系人的手机号}}// 开始合并map<int, vector<int>> unio; // 父节点和其子集map<string, vector<vector<string>>> res; // 一个名字可能对应多个通讯录号for (int i = 0; i < n; i++) {int cf = find(i); // 找到当前联系人的根节点unio[cf].push_back(i); // 合并到同一个集合}// 排序并输出结果for (auto& f : unio) {string cur_name;set<string> cur_phone; // 去重并排序手机号for (int c : f.second) {// 查询当前集合的名字最小值if (cur_name.size() == 0)cur_name = name[c];elsecur_name = min(cur_name, name[c]);// 合并当前联系人的所有手机号for (int i = 0; i < phone[c].size(); i++) {cur_phone.insert(phone[c][i]);}}vector<string> v_phone(cur_phone.begin(), cur_phone.end());res[cur_name].push_back(v_phone); // 保存结果}// 按姓名和手机号的ASCII码升序排序for (auto& t : res) {sort(t.second.begin(), t.second.end());for (auto c : t.second) {cout << t.first;for (int i = 0; i < c.size(); i++)cout << " " << c[i];cout << "\n";}}return 0;
}
