机试题——通讯录归并 - ToB企服应用市场:ToB评测及商务社交产业平台

4
kaka 10000000000 10000000001
tata 10000000020
kaka 10000000000 10000000002
tata 10000000010

复制代码

kaka 10000000000 10000000001 10000000002
tata 10000000010
tata 10000000020

复制代码

3
kaka 10000000000 10000000001
kaka 10000000001 10000000002
kaka 10000000002 10000000003

复制代码

kaka 10000000000 10000000001 10000000002 10000000003

复制代码

#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;
}

复制代码