题解 | #实体匹配结果归并与排序#

实体匹配结果归并与排序

https://www.nowcoder.com/practice/bc854ebbf5454e7b93e8d7f90faf1524

REALHW82 实体匹配结果归并与排序

题目链接

实体匹配结果归并与排序

题目描述

在数据治理平台中，不同的实体匹配引擎会各自产出“被认为指向同一真实实体”的编号集合。每一行输入代表某个引擎得到的一组编号（集合），行内的编号可能有重复。若两组集合存在至少一个公共编号，则它们应当被视作同一簇，需合并为一个更大的集合。

请你将所有集合按上述规则进行传递式合并与去重，并按指定顺序输出。

编号：仅由数字字符构成（如“1”“23”“0005”）。

排序规则

行内排序：将一个合并后的集合中的编号按字典序（字符串比较）升序排列后输出为一行。
行间排序：将所有行作为“编号有序序列”，按字典序（逐个编号从左到右比较）升序排列后输出。

输入描述: 第1行：整数 N，表示有 N 行匹配结果。接下来的 N 行：每行是若干个用空格分隔的数字字符串。

输出描述: 输出 M 行（M ≤ N）。每一行是一组经传递式合并与去重后的编号序列，满足“行内字典序、行间字典序”的排序要求。

解题思路

本题的核心是处理集合的传递性合并，这是一个经典的**并查集（Disjoint Set Union, DSU）**应用场景。解决步骤如下：

1. 元素映射

并查集是基于整数索引的数据结构，而本题的元素是字符串。因此，我们需要建立一个映射关系：

map<string, int> id_map: 将每个唯一的字符串编号映射到一个从 0 开始的整数 ID。
vector<string> name_map: 存储整数 ID 对应的原始字符串，用于最后的结果输出。

我们首先遍历所有输入，构建这两个映射表。

2. 并查集合并

初始化一个大小为唯一编号总数的并查集。
再次遍历每一行输入。对于行内的所有编号，将它们 union 到同一个集合中。具体操作是，将行内第一个编号作为代表，后续所有编号都与第一个编号进行合并。

3. 分组与去重

合并完成后，并查集中的每个连通分量就代表一个最终的簇。

创建一个 map<int, set<string>> groups，键是并查集中每个集合的根节点 ID，值是一个 set，用于存放该簇的所有成员字符串。使用 set 可以自动处理输入中可能存在的重复编号。
遍历所有唯一的字符串编号，通过 find 操作找到其根节点，然后将字符串加入对应根节点的 set 中。

4. 排序与输出

行内排序：将 groups 中的每个 set 转换成 vector。由于 set 本身是有序的，但其排序规则可能与题目的字符串字典序不同（例如 C++ 的 std::set），我们需要对 vector 进行一次字符串字典序排序。
行间排序：将所有排序好的 vector 放入一个 vector<vector<string>> 中，然后对这个外层 vector 进行排序。大多数语言的标准库对序列的排序默认就是字典序比较，可以直接使用。
最后，按排序后的顺序输出结果。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

// 字符串字典序比较
bool string_compare(const string& a, const string& b) {
    return a < b;
}

// 行间字典序比较
bool vector_compare(const vector<string>& a, const vector<string>& b) {
    return a < b;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    string line;
    getline(cin, line);
    n = stoi(line);

    vector<vector<string>> all_lines;
    map<string, int> id_map;
    int next_id = 0;

    for (int i = 0; i < n; ++i) {
        getline(cin, line);
        stringstream ss(line);
        string id;
        vector<string> current_line;
        while (ss >> id) {
            current_line.push_back(id);
            if (id_map.find(id) == id_map.end()) {
                id_map[id] = next_id++;
            }
        }
        all_lines.push_back(current_line);
    }

    if (next_id == 0) {
        return 0;
    }
    
    vector<string> name_map(next_id);
    for(auto const& [key, val] : id_map){
        name_map[val] = key;
    }

    DSU dsu(next_id);
    for (const auto& line_vec : all_lines) {
        if (line_vec.size() > 1) {
            int first_id = id_map[line_vec[0]];
            for (size_t i = 1; i < line_vec.size(); ++i) {
                dsu.unite(first_id, id_map[line_vec[i]]);
            }
        }
    }

    map<int, vector<string>> groups;
    for (int i = 0; i < next_id; ++i) {
        groups[dsu.find(i)].push_back(name_map[i]);
    }

    vector<vector<string>> result;
    for (auto const& [root, members] : groups) {
        vector<string> sorted_members = members;
        sort(sorted_members.begin(), sorted_members.end(), string_compare);
        result.push_back(sorted_members);
    }
    
    sort(result.begin(), result.end(), vector_compare);

    for (const auto& group : result) {
        for (size_t i = 0; i < group.size(); ++i) {
            cout << group[i] << (i == group.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

import java.util.*;

class DSU {
    private int[] parent;

    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public void unite(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        List<String[]> allLines = new ArrayList<>();
        Map<String, Integer> idMap = new HashMap<>();
        int nextId = 0;

        for (int i = 0; i < n; i++) {
            String[] ids = sc.nextLine().split(" ");
            allLines.add(ids);
            for (String id : ids) {
                if (!idMap.containsKey(id)) {
                    idMap.put(id, nextId++);
                }
            }
        }
        
        if (nextId == 0) return;

        String[] nameMap = new String[nextId];
        for (Map.Entry<String, Integer> entry : idMap.entrySet()) {
            nameMap[entry.getValue()] = entry.getKey();
        }

        DSU dsu = new DSU(nextId);
        for (String[] line : allLines) {
            if (line.length > 1) {
                int firstId = idMap.get(line[0]);
                for (int i = 1; i < line.length; i++) {
                    dsu.unite(firstId, idMap.get(line[i]));
                }
            }
        }

        Map<Integer, List<String>> groups = new HashMap<>();
        for (int i = 0; i < nextId; i++) {
            int root = dsu.find(i);
            groups.putIfAbsent(root, new ArrayList<>());
            groups.get(root).add(nameMap[i]);
        }

        List<List<String>> result = new ArrayList<>();
        for (List<String> members : groups.values()) {
            // 行内字典序排序
            members.sort(String::compareTo);
            result.add(members);
        }

        // 行间字典序排序
        result.sort((l1, l2) -> {
            int size = Math.min(l1.size(), l2.size());
            for (int i = 0; i < size; i++) {
                int cmp = l1.get(i).compareTo(l2.get(i));
                if (cmp != 0) return cmp;
            }
            return Integer.compare(l1.size(), l2.size());
        });

        for (List<String> group : result) {
            System.out.println(String.join(" ", group));
        }
    }
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j

def solve():
    n = int(input())
    all_lines = []
    id_map = {}
    next_id = 0

    for _ in range(n):
        ids = input().split()
        all_lines.append(ids)
        for id_str in ids:
            if id_str not in id_map:
                id_map[id_str] = next_id
                next_id += 1
    
    if next_id == 0:
        return

    name_map = {v: k for k, v in id_map.items()}

    dsu = DSU(next_id)
    for line in all_lines:
        if len(line) > 1:
            first_id = id_map[line[0]]
            for i in range(1, len(line)):
                dsu.union(first_id, id_map[line[i]])

    groups = {}
    for i in range(next_id):
        root = dsu.find(i)
        if root not in groups:
            groups[root] = []
        groups[root].append(name_map[i])
    
    result = []
    for root in groups:
        # 行内字典序排序
        sorted_members = sorted(groups[root])
        result.append(sorted_members)
        
    # 行间字典序排序 (Python默认的列表排序就是字典序)
    result.sort()

    for group in result:
        print(" ".join(group))

solve()

算法及复杂度

算法: 并查集 (Disjoint Set Union)
时间复杂度: $O(L + U \log U)$
- $L$ 是输入中所有编号的总出现次数, $U$ 是唯一编号的总数。
- 遍历输入、构建映射表： $O(L)$ 。
- 并查集合并： $O(L \cdot \alpha(U))$ ，其中 $\alpha$ 是反阿克曼函数，近乎常数。
- 分组： $O(U \cdot \alpha(U))$ 。
- 排序：对所有唯一编号进行行内和行间排序。总的排序复杂度主要由所有唯一编号决定，约为 $O(U \log U)$ 。
- 总体复杂度由遍历和排序主导。
空间复杂度: $O(U)$
- 需要存储字符串到整数的映射、并查集数组以及最终的分组结果，所有这些都与唯一编号的数量 $U$ 成正比。