题面解释:

题目要求我们整理一个通讯录，通讯录中的每个联系人包含姓名和若干个手机号。如果两个联系人有相同的手机号，则认为他们是同一个人，需要将他们合并为一个联系人。在合并时，如果发现姓名不同，则保留字典序较小的姓名，所有手机号合并后按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;
}

原始思路

• 最开始我的做法很笨：就是统计号码出现次数，用TreeMap统计的，都统计完后，如果该号码出现了两次及以上，就保留，如果小于两次就remove掉。
• 由此可以得到出现两次及以上的号码，通过遍历进行号码及联系人合并，并及时更新号码的出现次数，最后统计次数的集合为空时，代表合并完毕。
• 故得到了两个ArrayList：name与num，一一对应的，再组合到ans里排序，输出即可。
• 但是这样复杂度过高。

更新思路

• 后来想到，根据号码合并，类似把图联通，号码与人名之间相互联系，属于该人名的号码对应的下标也代表了其他人名,我存储数据时是按照下标一一照映存储的。
• 这样思路一下子就打开了，只需要统计下标之间的连通即可。
• 得到各自连通的后，进行遍历组合号码，挑选最小名字，并用memo记录是否统计过该下标，以防进入死循环，并把名字和号码组合到ans里面
• 最后把ans排序，输出即可。
• (没有看塔子哥的题解，自己想出的)

import java.util.*;
class Main{
   public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();

        String[] m;
        ArrayList<String> tempNa = new ArrayList<>();
        ArrayList<TreeSet<String>> tempNu = new ArrayList<>();
        Map<String, TreeSet<Integer>> numToIndex = new HashMap<>();
        ArrayList<ArrayList<String>> ans = new ArrayList<>();

        //存储数据  为
        //   姓名
        //   电话号码
        for (int i = 0; i < n; i++) {
            m = sc.nextLine().split(" ");
            String name = m[0];
            tempNa.add(name);
            tempNu.add(new TreeSet<>());
            for (int j = 1; j < m.length; j++) {
                if (!tempNu.get(i).contains(m[j])) {
                    //同一号码在同一个人身上最多出现一次吧
                    tempNu.get(i).add(m[j]);
                }
            }
        }
        //进行合并，
        //合并终止条件  num 中没有相同的

        ArrayList<ArrayList<Integer>> ansIndex = new ArrayList<>();
        for (int i = 0; i < tempNu.size(); i++) {
            //每个号码都对应了主人
            for (String nu : tempNu.get(i)) {
                if (!numToIndex.containsKey(nu)) {
                    TreeSet<Integer> temp = new TreeSet<>();
                    temp.add(i);
                    numToIndex.put(nu, temp);
                } else {
                    numToIndex.get(nu).add(i);
                }
            }
        }
        int[] memo = new int[tempNa.size()];
        for (int i = 0; i < tempNa.size(); i++) {
            TreeSet<String> name = new TreeSet<>();
            TreeSet<String> num = new TreeSet<>();
            Queue<Integer> q = new LinkedList<>();

            if (memo[i] != 1) {
                q.add(i);
                while (!q.isEmpty()) {
                    int qq = q.poll();
                    if (memo[qq] != 1) {
                        //未访问过
                        memo[qq] = 1;
                        name.add(tempNa.get(qq));
                        num.addAll(tempNu.get(qq));
                        for (String nu : tempNu.get(qq)) {
                            q.addAll(numToIndex.get(nu));
                        }
                    }
                }
                //找到连在一起的名字以及号码
                ArrayList<String> numA = new ArrayList<>(num);
                numA.add(0, name.first());
                ans.add(numA);
            }

        }

        ans.sort((o1, o2) -> {
            if (o1.get(0).equals(o2.get(0))) {
                return o1.get(1).compareTo(o2.get(1));
            }
            return o1.get(0).compareTo(o2.get(0));
        });
        int i = 0;
        for (ArrayList<String> a : ans) {
            if (i++ > 0) {
                System.out.println();
            }
            for (int j = 0; j < a.size(); j++) {
                System.out.print((j == 0 ? "" : " ") + a.get(j));
            }
        }

    }
}

#include<bits/stdc++.h>
using namespace std;
int N,num=0;
struct STU{
	string name;
	set<string>st;
}stu[1010],st[1010];
bool cmp(const STU&a,const STU&b){
	if(a.name<b.name)return 1;
	if(a.name>b.name)return 0;
	return *a.st.begin()<*b.st.begin();
}
int fa[1010];
int Find(int x){
	if(fa[x]!=x)fa[x]=Find(fa[x]);
	return fa[x];
}
void Merge(int x,int y){
	int f=Find(fa[x]),g=Find(fa[y]);
	fa[f]=g;
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>N;
	string s;
	getline(cin,s);
	int num_stu=0;
	for(int i=1;i<=N;i++){
		stringstream v; v.clear();
		getline(cin,s);
		v<<s;
		v>>stu[++num_stu].name;
		while(v>>s) stu[num_stu].st.insert(s);
	}
	for(int i=1;i<=num_stu;i++)fa[i]=i;
	for(int i=1;i<=num_stu;i++){
		for(int j=1;j<=num_stu;j++){
			if(i==j||Find(i)==Find(j))continue;
			for(auto&u:stu[i].st){
				if(stu[j].st.find(u)!=stu[j].st.end()){
					Merge(i,j);
					break;
				}
			}
		}
	}
	int num_st=0;
	for(int i=1;i<=num_stu;i++){
		if(Find(i)==i){
			for(int j=1;j<=num_stu;j++){
				if(Find(j)==i){
					if(stu[j].name<stu[i].name)
						stu[i].name=stu[j].name;
					for(auto&u:stu[j].st)
						stu[i].st.insert(u);
				}
			}
			st[++num_st].name=stu[i].name;
			st[num_st].st=stu[i].st;
		}
	}
	sort(st+1,st+num_st+1,cmp);
	for(int i=1;i<=num_st;i++){
		cout<<st[i].name<<" ";
		for(auto&u:st[i].st)cout<<u<<" ";
		cout<<endl;
	}
	return 0;
}