num = int(input())
data = [list(input().split()) for _ in range(num)]
phone_to_id = {}
for i in range(num):
    for phone in data[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 fa[x]!=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

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_phone = {}

for i in range(num):
    root = find(i)
    if root in root_to_name:
        if data[i][0]<=root_to_name[root]:
            root_to_name[root]=data[i][0]
    else:
        root_to_name[root]=data[i][0]
    
    for phone in data[i][1:]:
        if root in root_to_phone:
            root_to_phone[root].add(phone)
        else:
            root_to_phone[root]= {phone}
res=[]
for root in root_to_name:
    res += [[root_to_name[root]]+sorted(list(root_to_phone[root]))]
res.sort()
for line in res:
    print(' '.join(line))

# 判断某两行数据是否具有相同phone number
def have_same_num(info1, info2):
    return len(set(info1[1:]) & set(info2[1:])) != 0

# 读取输入
num = int(input().strip())
arr = list()
for i in range(num):
    arr.append(input().strip().split())

# 倒序遍历列表
# 每个元素先弹出，如果其上方子列表存在相同号码则合并（合并时若username不同则取较小）
# 否则不合并，放回原列表
for i in range(len(arr)-1, 0, -1):
    info = arr.pop(i)
    flag_combine = 0
    for j in range(len(arr)):
        if have_same_num(info, arr[j]):
            arr[j][0] = min(arr[j][0], info[0])
            arr[j].extend(info[1:])
            flag_combine = 1
            break
    if not flag_combine:
        arr.append(info)

# 排序
book = []
for info in arr:
    book.append([info[0], sorted(set(info[1:]))])
book = sorted(book)

# 打印
for info in book:
    print(info[0], end=' ')
    print(*info[1])

题面解释:

你有一个通讯录，其中每个联系人包含姓名和多个手机号。如果两个联系人拥有相同的手机号，认为他们是同一个人，需要将其合并。如果合并时发现姓名不同，则保留字典序较小的姓名。通讯录中记录的手机号最多有10个，且每个手机号由1到10位数字组成。输入第一行为记录数量，接下来每行为一条联系人记录，包含姓名和若干手机号，手机号之间用空格隔开。输出时，整理后的通讯录需要按姓名字典序排列，同一联系人的手机号也按升序排列。

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

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

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

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

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

题解

题目分析

题目要求我们对通讯录中的联系人进行合并，如果发现两个联系人有相同的电话号码，则认为他们是同一个人。合并后的联系人需要保留字典序最小的姓名，且所有电话号码按字典序排列。

这道题的核心在于如何高效地合并具有相同电话号码的联系人。我们可以利用并查集来处理这种合并问题，结合电话号码映射联系人，实现联系人信息的合并与整理。

思路步骤

1. 并查集的使用：

   • 每个联系人初始时自己是一个独立的集合，我们将通过电话号码来判断哪些联系人属于同一个集合。如果两个联系人有相同的电话号码，则他们应该属于同一个集合，使用并查集进行合并。

2. 电话号码映射到联系人：

   • 我们使用一个哈希表，存储电话号码与联系人编号的映射。如果发现某个号码已经属于某个联系人编号，则合并当前联系人和对应联系人。

3. 合并后的联系人处理：

   • 在并查集中的每个集合里，找到字典序最小的姓名，并且合并所有电话号码。
   • 电话号码合并后需要进行去重，并按字典序排序。

4. 输出排序：

   • 对最终的合并结果按姓名和电话号码进行排序，并输出。

复杂度分析：

• 时间复杂度：主要是并查集的合并和查找操作，其均摊时间复杂度为 O(α(n))，几乎接近常数。此外，还需对所有联系人进行排序，总复杂度为 O(n log n)。

• 空间复杂度：O(n) 用于存储联系人信息和并查集的辅助数组。

代码如下

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;  // 电话号码集合
} 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);
    int rootY = findParent(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());
    string minPhoneB = *(b.phones.begin());
    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;
}