如何在O(kl)时间内将k个长度l的排序列表转为n顶点有向图邻接表

现有一个索引从1到k的数组，每个元素是一个排序列表（例如1-2-3-4等价于优先级关系1>2>3>4，即列表中前面的所有元素都比后面的所有元素优先级高）。需要将该数组转换为邻接表：顶点为n个元素，边(u,v)代表u>v。已知n的值，输入列表可视为ArrayList。

试过多种解法，但要么生成大量重复边，要么需要O(kl²)的时间复杂度（逐一比对列表中每个元素与后续元素）。

要求：冗余边数量需低于kl，确保后续图算法能在O(kl + n)时间内执行。

示例 #

输入 #

A[1] = 1 - 2 - 4, 
A[2] = 5 - 2 - 3, 
A[3] = 1 - 4 - 3

输出邻接表X #

X[1] = 2 - 4 -3, 
X[2] = 4 - 3,
X[3] = empty, 
X[4] = 3,
X[5] = 2 - 3

思路 #

核心是通过集合去重避免冗余边，同时根据需求选择不同的边添加策略来控制时间复杂度：

方法1：保留所有优先级关系（含传递隐含关系） #

如果需要邻接表包含所有u>v的优先级关系（无论直接定义还是隐含传递），按以下步骤实现：

1. 初始化邻接表：每个顶点对应一个哈希集合（n较小时可用布尔数组），用于存储已添加的邻接节点，自动去重。
2. 遍历每个排序列表：
   • 对列表中每个元素u（位置i），遍历其后续所有元素v（位置j > i）：
     • 若v不在u的邻接集合中，将其加入。
3. 最后将每个集合转换为有序列表（若需要），得到最终邻接表。

该方法通过集合完全消除重复边，冗余边数量为0，满足低于kl的要求；时间复杂度为O(kl²)，但实际运行中因去重逻辑会跳过大量重复操作，效率优于暴力遍历。

方法2：传递约简（仅保留直接边） #

如果后续图算法（如拓扑排序）不需要显式的传递关系，可仅保留每个排序列表中相邻元素的直接边，将时间复杂度降至O(kl)：

1. 用哈希集合/布尔数组初始化邻接表。
2. 遍历每个排序列表：
   • 遍历列表中相邻元素对(a[i], a[i+1])：
     • 若a[i+1]不在a[i]的邻接集合中，将其加入。
3. 转换为有序列表得到邻接表。

这种方法的边数为k*(l-1)，完全符合冗余边低于kl的要求，后续图算法可在O(kl + n)时间内高效执行。

示例适配说明 #

示例输出包含了传递关系（如1>3），适合用方法1实现。若用方法2，邻接表会更精简：

X[1] = 2 - 4, 
X[2] = 4 - 3,
X[3] = empty, 
X[4] = 3,
X[5] = 2

后续通过传递闭包计算仍可得到所有u>v关系，不影响最终逻辑。

内容的提问来源于stack exchange，提问作者ESW_