题目描述
你有一个通讯录，每个联系人包含姓名和手机号，一个联系人可能有多个手机号。如果两个联系人拥有相同的手机号，我们认为他们是同一个人。任务是整理通讯录，将具有相同手机号的联系人合并为一个联系人，并返回合并后的通讯录列表。如果合并时发现联系人姓名不同，以字典序小的为姓名。
输入描述
- 第一行：一个整数
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];
else
cur_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;
}