题面解释:

题目要求我们整理一个通讯录，通讯录中的每个联系人包含姓名和若干个手机号。如果两个联系人有相同的手机号，则认为他们是同一个人，需要将他们合并为一个联系人。在合并时，如果发现姓名不同，则保留字典序较小的姓名，所有手机号合并后按ASCII码升序排列。输入包括通讯录的记录数量$num$（范围为1到1000），后续每一行表示一个联系人，包含姓名和若干手机号（每个手机号不超过10个，长度为1到10位）。输出要求合并后的联系人列表，并按ASCII码顺序输出姓名及其手机号。

思路:并查集 + 哈希 + 自定义排序

1.基于共享电话号码的联系人属于同一组的思路，我们可以先使用哈希表将电话号码映射到对应的联系人编号列表上，然后使用并查集将共享同一电话号码的联系人合并到同一组。

2.对于并查集里的每个组（用该集合中的root节点编号表示），我们需要找到字典序最小的联系人姓名和该组内的联系人的所有电话号码。

我们可以使用一个哈希表来存储每个组（用该集合中的root节点编号表示）的最小字典序的姓名和所有电话号码。

3.最后，我们将每个组的姓名及电话号码（按字典序排序）存储到结果列表中，并对结果列表进行一个字典序排序。

1. 使用并查集解决分组问题

• 并查集是解决动态连通性问题的经典数据结构。在本题中，我们可以将每个联系人看作一个独立的节点，如果两个联系人有相同的电话号码，则将他们视为连通的，这样可以将拥有相同电话号码的联系人合并为同一组。

• 每个联系人初始时都是独立的，我们将每个联系人看作一个集合的根节点。之后，我们通过遍历所有联系人，找到具有相同手机号的联系人并进行合并操作。

2. 处理分组后的姓名和电话号码

• 每个分组中的联系人可能有不同的姓名。根据题目要求，我们需要保留字典序较小的姓名。
• 另外，分组后的联系人可能有多个电话号码，我们需要将这些电话号码合并，并按字典序进行排序。

3. 输出结果

• 最终输出要求按姓名的字典序进行排序。我们先将所有分组进行合并处理，随后对合并后的结果进行排序并输出。

代码解析

1. 并查集部分：

   • findParent(x)：通过路径压缩查找某个节点的根节点。
   • unionGroups(x, y)：合并两个联系人组。

2. 联系人信息处理部分：

   • 通过getline()获取每一行输入并解析出姓名和电话号码。
   • 将姓名存储到Contact结构体中的name字段，电话号码存储到set<string>中，利用set自动去重并保持顺序。

3. 合并联系人部分：

   • 通过并查集，将具有相同电话号码的联系人合并为一组。如果发现多个联系人共享同一组，则选择字典序较小的姓名，并合并所有电话号码。

4. 排序输出部分：

   • 使用sort()函数按姓名的字典序进行排序，姓名相同时按最小的电话号码排序。
   • 最后输出结果，姓名和电话号码以空格分隔。

代码如下

python

# 输入联系人数量
num = int(input())

# 输入联系人姓名及其电话号码，并按行存储
arr = [input().split() for _ in range(num)]

# 创建一个字典，用于映射电话号码到对应的联系人编号列表
phone_to_id = {}

# 遍历每个联系人，将他们的电话号码加入映射字典中
for i in range(num):
    for phone in arr[i][1:]:
        if phone in phone_to_id:
            # 如果电话号码已经存在，添加当前联系人编号到列表中
            phone_to_id[phone].append(i)
        else:
            # 如果电话号码不存在，初始化一个列表并存储联系人编号
            phone_to_id[phone] = [i]

# 初始化并查集，每个联系人最初是自己所在组的代表
fa = [i for i in range(num)]

# 查找函数（带路径压缩），查找当前联系人所在组的根节点
def find(x):
    if x != fa[x]:
        fa[x] = find(fa[x])  # 路径压缩
    return fa[x]

# 合并两个组，将两个联系人的组合并到一起
def merge(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        fa[x] = y  # 合并操作

# 判断两个联系人是否属于同一组
def same(x, y):
    return find(x) == find(y)

# 遍历每个电话号码，将共享同一电话号码的联系人合并到同一组
for phone in phone_to_id:
    first_id = phone_to_id[phone][0]  # 获取第一个联系人的编号
    for i in range(1, len(phone_to_id[phone])):
        merge(first_id, phone_to_id[phone][i])  # 合并其他拥有相同电话号码的联系人

# 创建字典，用于存储每个组的最小字典序的姓名和所有电话号码
root_to_name = {}
root_to_phones = {}

# 遍历每个联系人，按组进行合并处理
for i in range(num):
    root = find(i)  # 查找联系人的根节点（代表组）

    # 如果该组已经有一个名字，则比较字典序
    if root in root_to_name:
        # 更新为字典序更小的姓名
        if arr[i][0] <= root_to_name[root]:
            root_to_name[root] = arr[i][0]
    else:
        # 如果该组还没有姓名，则赋值当前联系人的姓名
        root_to_name[root] = arr[i][0]

    # 合并该联系人的所有电话号码到所在组
    for phone in arr[i][1:]:
        if root in root_to_phones:
            # 如果该组已经有电话号码，则继续添加
            root_to_phones[root].add(phone)
        else:
            # 如果该组没有电话号码，则初始化一个集合并添加
            root_to_phones[root] = {phone}

# 结果存储列表
res = []

# 构建结果列表，包含每个组的姓名及电话号码（按字典序排序）
for root in root_to_name:
    res.append([root_to_name[root]] + sorted(list(root_to_phones[root])))

# 对结果列表进行排序
res.sort()

# 输出合并后的联系人姓名及电话号码
for x in res:
    print(' '.join(x))

java

import java.util.*;





public class Main {
    static int[] parent;

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

    public static void union(int x, int y){
        parent[find(x)] = find(y);
    }

    static class Contact{
        String name;//联系人姓名
        Set<String> phoneNum;//联系人电话
        int id;

        Contact(String name,Set<String> phoneNum,int id){
            this.name = name;
            this.phoneNum = phoneNum;
            this.id = id;
        }
    }
    //合并后
    static class MergedContact{
        String name;
        Set<String> phoneNum;

        MergedContact(String name,Set<String> phoneNum){
            this.name = name;
            this.phoneNum = phoneNum;
        }

        String getMinPhoneNumber(){
            return Collections.min(phoneNum);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //记录数量
        int recordCount = sc.nextInt();
        sc.nextLine();
        //联系人列表
        List<Contact> contacts = new ArrayList<>();
        parent = new int[recordCount];

        //初始化并查集
        for(int i=0;i<recordCount;i++){
            parent[i] = i;
        }

        Map<String,Integer> phoneToContactId = new HashMap<>();

        for (int i = 0; i < recordCount; i++) {
            String input = sc.nextLine().trim();
            String[] tokens = input.trim().split("\\s+");
            String name = tokens[0];

            Set<String> phoneNumber = new HashSet<>();
            for (int j = 1; j < tokens.length; j++) {
                String phone = tokens[j];
                phoneNumber.add(phone);
                if (!phoneToContactId.containsKey(phone)) {
                    phoneToContactId.put(phone, i);
                } else {
                    int otherId = phoneToContactId.get(phone);
                    union(i, otherId);
                }
            }
            contacts.add(new Contact(name, phoneNumber, i));
        }
        //合并联系人
        Map<Integer,MergedContact> rootIdToMergedContact = new HashMap<>();
        for(int i=0;i<recordCount;i++){
            int root  = find(i);
            Contact contact = contacts.get(i);
            if(!rootIdToMergedContact.containsKey(root)){
                rootIdToMergedContact.put(root,new MergedContact(contact.name,new HashSet<>(contact.phoneNum)));
            }else{
                MergedContact mergedContact = rootIdToMergedContact.get(root);
                //更新姓名
                if(contact.name.compareTo(mergedContact.name) < 0){
                    mergedContact.name = contact.name;
                }
                mergedContact.phoneNum.addAll(contact.phoneNum);
            }
        }

        List<MergedContact> mergedContacts = new ArrayList<>(rootIdToMergedContact.values());
        for(MergedContact mc : mergedContacts){
            //将电话号码集改为TreeSet进行排序
            mc.phoneNum = new TreeSet<>(mc.phoneNum);
        }

        mergedContacts.sort((a,b)->{
            int nameCompare = a.name.compareTo(b.name);
            if(nameCompare!=0){
                return nameCompare;
            }else {
                String minPhoneA = a.getMinPhoneNumber();
                String minPhoneB = b.getMinPhoneNumber();
                return minPhoneA.compareTo(minPhoneB);
            }
        });

        for(MergedContact mc:mergedContacts){
           StringBuilder sb = new StringBuilder();
           sb.append(mc.name);

            List<String> sortedphones = new ArrayList<>(mc.phoneNum);
            Collections.sort(sortedphones);
            for(String phone : sortedphones){
                sb.append(" ").append(phone);
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }

}

cpp

#include <bits/stdc++.h>
using namespace std;

int parent[1005];  // 并查集数组，用于存储每个联系人的父节点
int visited[1005]; // 记录某个联系人组是否已经处理过
struct Contact {
    int id;              // 联系人编号
    string name;         // 联系人姓名
    set<string> phones;  // 电话号码集合，使用set确保电话号码不重复且方便排序
} contacts[1005], mergedContacts[1005];
int mergedCount = 0;    // 合并后的联系人数量

// 并查集的查找操作，查找 x 的根节点
int findParent(int x) {
    if (parent[x] == x) return x;  // 如果当前节点是根节点，直接返回
    return parent[x] = findParent(parent[x]);  // 路径压缩优化，使查找效率更高
}

// 并查集的合并操作，将 x 和 y 所在的组合并
void unionGroups(int x, int y) {
    int rootX = findParent(x);  // 查找 x 的根节点
    int rootY = findParent(y);  // 查找 y 的根节点
    if (rootX != rootY) {
        parent[rootX] = rootY;  // 将 x 所在的组的根节点指向 y 所在组的根节点
    }
}

// 比较函数，用于对联系人进行排序
bool compareContacts(Contact a, Contact b) {
    if (a.name != b.name) return a.name < b.name;  // 如果姓名不同，按姓名的字典序排序
    string minPhoneA = *(a.phones.begin());  // 获取 a 的最小电话号码
    string minPhoneB = *(b.phones.begin());  // 获取 b 的最小电话号码
    return minPhoneA < minPhoneB;  // 如果姓名相同，按最小电话号码的字典序排序
}

int main() {
    int n;  // 联系人数
    cin >> n;

    // 初始化并查集，每个联系人初始时自己是自己的父节点
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    string inputLine;
    getline(cin, inputLine);  // 吃掉换行符，避免之后的输入错误
    for (int i = 1; i <= n; i++) {
        getline(cin, inputLine);  // 读取每一行的联系人信息
        int length = inputLine.length();

        Contact contact = {};  // 新建一个联系人对象
        int wordCount = 0;
        string word = "";

        // 解析输入，将姓名和电话号码分割存储
        for (int j = 0; j < length; j++) {
            word += inputLine[j];  // 构建单词
            if (j == length - 1 || inputLine[j + 1] == ' ') {
                if (wordCount == 0) {
                    contact.name = word;  // 第一个单词为姓名
                } else {
                    contact.phones.insert(word);  // 后续的为电话号码，存入集合
                }
                wordCount++;  // 单词计数
                word = "";  // 重置单词
                j++;  // 跳过空格
            }
        }

        contacts[i] = contact;  // 存储联系人信息

        // 合并当前联系人与前面所有联系人，检查是否有相同的电话号码
        for (int j = 1; j < i; j++) {
            for (const string &phoneJ : contacts[j].phones) {
                for (const string &phoneI : contact.phones) {
                    if (phoneJ == phoneI) {
                        unionGroups(j, i);  // 如果有相同号码则合并到同一组
                    }
                }
            }
        }
    }

    // 将联系人进行合并
    for (int i = 1; i <= n; i++) {
        int root = findParent(i);  // 找到联系人所在的组
        if (visited[root] == 0) {  // 如果该组未处理过
            mergedContacts[++mergedCount] = contacts[i];  // 新组加入联系人
            visited[root] = mergedCount;  // 标记该组已处理
        } else {
            // 如果该组已存在联系人，则合并信息
            if (contacts[i].name < mergedContacts[visited[root]].name) {
                mergedContacts[visited[root]].name = contacts[i].name;  // 更新为字典序较小的姓名
            }
            // 合并电话号码
            for (const string &phone : contacts[i].phones) {
                mergedContacts[visited[root]].phones.insert(phone);
            }
        }
    }

    // 按规则排序联系人
    sort(mergedContacts + 1, mergedContacts + mergedCount + 1, compareContacts);

    // 输出结果
    for (int i = 1; i <= mergedCount; i++) {
        cout << mergedContacts[i].name << ' ';
        for (const string &phone : mergedContacts[i].phones) {
            cout << phone << ' ';
        }
        cout << '\n';
    }

    return 0;
}

题目内容

你有一个通讯录，这个通讯录里每个联系人都包含姓名和手机号，一个联系人可能有多个手机号。

如果发现两个联系人拥有相同的手机号，我们就认为他们是同一个人。

你的任务就是整理这个通讯录，将具有相同手机号的联系人合并为一个联系人，并返回合并后的通讯录列表。

注意：用例不保证具有相同手机号的联系人姓名肯定是相同的，如果合并的时候发现联系人姓名不同，那么以字典序小的为姓名。

输入描述

第一行表示通讯录的记录数量$num$，值的范围[$1, 1000$]。

从第二行开始，每一行代表一条联系人记录，每条录包括姓名和若干电话号码，电话号码的个数不超过$10$（姓名由英文字母大小写组成，长度在1到10之间，电话号码由数字组成）。

之后的若干条记录代表人的记录（手机号个数$1$到$10$位数字不重复）。同一条记录里的电话号码用空格隔开，电话号码的长度在[$1,10$]

输出描述

整理后的通讯录列表，其中如果两个联系人被识别为同一个人，则他们的电话号码合并。

输出联系人姓名和手机号码列表按$ASCII$码升序排序。

样例1

输入

4 
kaka 10000000000 10000000001 
tata 10000000020 
kaka 10000000000 10000000002 
tata 10000000010

输出

kaka 10000000000 10000000001 10000000002 
tata 10000000010 
tata 10000000020 

说明

在这个通讯录中，第一个kaka和第二个kaka有相同的手机号“10000000000”，因此他们被视为同一个人。

因此kaka一共有三个号码并按ASCII码升级排序结果是10000000000 10000000001 10000000002。

第一个tata和第二个tata没有相同的号码，因此被视作两个人。

样例2

输入

3
kaka 10000000000 10000000001
kaka 10000000001 10000000002
kaka 10000000002 10000000003

输出

kaka 10000000000 10000000001 10000000002 10000000003

说明

在这个通讯录中，第一个kaka和第二个kaka有相同的手机号“10000000001”，第二个kaka和第三个kaka有相同的手机号“10000000002”，因此题目被视为同一个人。

因此kaka一共有四个号码并按ASCII码升级排序结果是10000000000 10000000001 10000000002 10000000003