解题思路

题意要求将多个实体匹配系统输出的实体结果进行去重、合并与排序。 每个系统的输出可视为一个集合，若两个集合存在交集，则它们应被合并为一个更大的集合。

这实际上是一个并查集（Union-Find） 的典型应用场景：

• 每个实体可以看作一个节点；
• 若两个实体在同一系统结果中出现，则它们属于同一连通分量；
• 通过并查集合并所有出现在同一行的实体；
• 最后，将所有节点根据其根节点分组，输出每个连通分量（集合）内的实体。

实现步骤

1. 读取输入的系统数 N；

2. 对每一行实体结果：

   • 将该行所有实体放入列表；
   • 使用并查集，将该行所有实体合并到同一集合中；

3. 最终遍历所有实体，按根节点进行归类；

4. 对每个集合内的实体进行字典序排序；

5. 对所有集合按字典序整体排序；

6. 输出结果。

复杂度分析

• 时间复杂度： 每次合并操作近似为常数时间（路径压缩优化），总复杂度约为 O(T * α(N))，其中 T 为所有实体出现次数（≤100000），α(N) 为阿克曼函数，几乎可视为常数。 排序部分复杂度为 O(K log K)，K 为最终集合内的元素数。 综合复杂度为 O(N log N)。

• 空间复杂度： 存储并查集及映射关系，约为 O(N)，符合题目要求。

代码实现

Python 实现

# 并查集实现类
class UnionFind:
    def __init__(self):
        self.parent = {}

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[py] = px

def merge_entities(n, systems):
    uf = UnionFind()
    # 初始化所有实体
    for line in systems:
        for entity in line:
            if entity not in uf.parent:
                uf.parent[entity] = entity

    # 按每行进行合并
    for line in systems:
        base = line[0]
        for entity in line[1:]:
            uf.union(base, entity)

    # 收集每个集合
    groups = {}
    for entity in uf.parent:
        root = uf.find(entity)
        groups.setdefault(root, set()).add(entity)

    # 按题意要求排序
    result = []
    for group in groups.values():
        sorted_group = sorted(group)
        result.append(sorted_group)
    result.sort()

    return result

if __name__ == "__main__":
    n = int(input())
    systems = []
    for _ in range(n):
        line = input().strip().split()
        if line:
            systems.append(line)

    merged = merge_entities(n, systems)
    for group in merged:
        print(" ".join(group))

Java 实现

import java.util.*;

public class Main {
    // 并查集：用于把同一行出现的实体合并到同一个集合
    static class UnionFind {
        Map<String, String> parent = new HashMap<>();

        // 查找（带路径压缩）
        String find(String x) {
            if (!parent.get(x).equals(x)) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }

        // 合并
        void union(String a, String b) {
            String pa = find(a), pb = find(b);
            if (!pa.equals(pb)) parent.put(pb, pa);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取系统数量
        int n = Integer.parseInt(sc.nextLine());
        UnionFind uf = new UnionFind();
        List<List<String>> systems = new ArrayList<>();

        // 读取每行系统输出（实体用空格分隔）
        for (int i = 0; i < n; i++) {
            if (!sc.hasNextLine()) break;
            String line = sc.nextLine().trim();
            if (line.isEmpty()) continue;  // 跳过空行
            // 使用 \\s+ 以容忍多空格
            String[] parts = line.split("\\s+");
            List<String> list = Arrays.asList(parts);
            systems.add(list);
            // 初始化并查集中的节点
            for (String s : list) uf.parent.putIfAbsent(s, s);
        }

        // 每行内的实体合并为同一集合
        for (List<String> list : systems) {
            if (list.isEmpty()) continue;
            String base = list.get(0);
            for (int j = 1; j < list.size(); j++) {
                uf.union(base, list.get(j));
            }
        }

        // 按根结点分组
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : uf.parent.keySet()) {
            String root = uf.find(s);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(s);
        }

        // ===== 关键改动：按“字典序（字符串比较）”排序 =====
        // 1) 组内：Collections.sort -> 字符串自然顺序（字典序）
        List<List<String>> res = new ArrayList<>();
        for (List<String> g : groups.values()) {
            Collections.sort(g);   // 组内字典序
            res.add(g);
        }

        // 2) 组间：逐元素字符串比较的字典序
        res.sort((a, b) -> {
            int len = Math.min(a.size(), b.size());
            for (int i = 0; i < len; i++) {
                int cmp = a.get(i).compareTo(b.get(i)); // 字典序逐元素比较
                if (cmp != 0) return cmp;
            }
            return Integer.compare(a.size(), b.size()); // 前缀相同则短的在前
        });

        // 输出
        for (List<String> list : res) {
            System.out.println(String.join(" ", list));
        }

        sc.close();
    }
}

C++ 实现

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

// 并查集结构体
struct UnionFind {
    unordered_map<string, string> parent;

    // 查找根节点（带路径压缩）
    string find(const string &x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并两个节点
    void unite(const string &a, const string &b) {
        string pa = find(a), pb = find(b);
        if (pa != pb) parent[pb] = pa;
    }
};

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

    int n;
    cin >> n;
    cin.ignore(); // 忽略换行符

    UnionFind uf;
    vector<vector<string>> systems; // 存储每个系统的匹配结果

    // 读取输入
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        if (line.empty()) continue;
        stringstream ss(line);
        string x;
        vector<string> temp;

        // 分割实体
        while (ss >> x) {
            temp.push_back(x);
            if (!uf.parent.count(x))
                uf.parent[x] = x; // 初始化父节点
        }
        systems.push_back(temp);
    }

    // 合并每一行中的实体集合
    for (auto &v : systems) {
        for (size_t j = 1; j < v.size(); j++)
            uf.unite(v[0], v[j]);
    }

    // 根据根节点分组
    map<string, set<string>> groups;
    for (auto &p : uf.parent) {
        string root = uf.find(p.first);
        groups[root].insert(p.first);
    }

    // 转换为 vector 并排序输出
    vector<vector<string>> res;
    for (auto &it : groups) {
        vector<string> tmp(it.second.begin(), it.second.end());
        sort(tmp.begin(), tmp.end());
        res.push_back(tmp);
    }

    // 按字典序排序所有集合
    sort(res.begin(), res.end());

    // 输出结果
    for (auto &v : res) {
        for (size_t i = 0; i < v.size(); i++) {
            if (i) cout << " ";
            cout << v[i];
        }
        cout << "\n";
    }

    return 0;
}

题目内容

某业务部门有多个数据来源，现在需要对多个来源的实体数据进行去重、消歧、合并。有多个实体匹配系统（假设系统的匹配结果完全正确），每个系统从不同角度进行匹配，匹配结果是相同实体列表。

这些匹配结果中往往存在交叉重复的问题，需要对所有匹配结果进行合并去重。例如系统 $A$ 的匹配结果是 ["$1$", "$2$"] ，系统 $B$ 的匹配结果是 ["$2$", "$3$"]，那么合并后的匹配结果是 ["$1$", "$2$", "$3$"]。请你按照上述逻辑，编写代码实现对匹配结果的合并去重。

输入描述

• 第一行输入是整数 $N$，表示有 $N$ 个实体匹配系统，$1<=N<=10000$ ；

• 接下来 $N$ 行是每个实体匹配系统的匹配结果（相同实体列表，每行实体数量不超过 $100$ ）；实体使用数字字符串表示（字符长度不超过 $10$），实体之间通过空格分开。实体种类数量不超过 $100000$ 。

输出描述

输出 $M$ 行（$M <= N$），每行内容是合并后的匹配结果。

注意，每行的输出结果需要按照字典顺序进行排序；合并后的匹配结果列表之间，也需要按字典顺序进行排序。

样例1

输入

5
1 2 3
4 5
11 22
33 44 55 1
3 66

输出

1 2 3 33 44 55 66
11 22
4 5

说明

匹配结果 "$1$ $2$ $3$ "、"$33$ $44$ $55$ $1$"、"$3$ $66$"，存在重复实体 "$1$" 和 "$3$"，故可以合并，合并后按字典序为 "$1$ $2$ $3$ $33$ $44$ $55$ $66$"；

另外两组结果与其他组不存在重复；

合并后的匹配结果列表之间，按字典序排序后输出，即样例输出所示内容。

样例2

输入

2
1 2
2 3

输出

1 2 3

说明

有两组匹配结果，即 "$1$ $2$"和"$2$ $3$"，存在重复实体 "$2$"，故可以合并为 "$1$ $2$ $3$"。