拓扑排序的存在性和唯一性;建图的CornerCase

  |  

摘要: 建图的各种 Corner Case

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们通过一个拓扑排序的应用问题,看一下在建图时可能遇到的各种 Corner Case。此外本题还有一个值得注意的点是拓扑排序唯一性的判定问题。

$1 题目

给定一个长度为 n 的整数数组 nums ,其中 nums 是范围为 [1,n] 的整数的排列。还提供了一个 2D 整数数组 sequences ,其中 sequences[i] 是 nums 的子序列。

检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列,并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ,可能存在多个有效的 超序列 。

  • 例如,对于 sequences = [[1,2],[1,3]] ,有两个最短的 超序列 ,[1,2,3] 和 [1,3,2] 。
  • 而对于 sequences = [[1,2],[1,3],[1,2,3]] ,唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列,但不是最短的。

如果 nums 是序列的唯一最短 超序列 ,则返回 true ,否则返回 false 。

子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素,而不改变其余元素的顺序的序列。

示例 1:
输入:nums = [1,2,3], sequences = [[1,2],[1,3]]
输出:false
解释:有两种可能的超序列:[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列,所以返回false。

示例 2:
输入:nums = [1,2,3], sequences = [[1,2]]
输出:false
解释:最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列:[1,2]。
因为 nums 不是最短的超序列,所以返回false。

示例 3:
输入:nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出:true
解释:最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列:[1,2,3]。
序列 [1,3] 是它的一个子序列:[1,2,3]。
序列 [2,3] 是它的一个子序列:[1,2,3]。
因为 nums 是唯一最短的超序列,所以返回true。

提示:

1
2
3
4
5
6
7
8
9
n == nums.length
1 <= n <= 1e4
nums 是 [1, n] 范围内所有整数的排列
1 <= sequences.length <= 1e4
1 <= sequences[i].length <= 1e4
1 <= sum(sequences[i].length) <= 105
1 <= sequences[i][j] <= n
sequences 的所有数组都是 唯一 的
sequences[i] 是 nums 的一个子序列

$2 题解

算法:建图 + 拓扑排序

seqs 可以重建 org,也就是 seqs 的最短公共超序列等于 org,等价于以下条件均成立:

1
2
3
4
考察 seqs 的拓扑排序
1. 拓扑排序存在
2. 拓扑排序唯一
3. 拓扑排序序列等于 org

拓扑排序的存在性和唯一性判定

  • 执行拓扑排序的过程中,如果最终的拓扑排序序列长度不为 n,则拓扑排序不存在
  • BFS 拓扑排序过程中,如果队列长度始终唯一,则出入队的顺序唯一

整体流程:

  • step1: 建图
  • step2: 执行拓扑排序,过程中实时判断队列长度
  • step3: 对比拓扑排序序列和 org 序列

拓扑排序的部分算法与实现参考 BFS拓扑排序

建图的部分比较复杂,因为有各种 corner case

1
2
3
4
(1) seqs = [],办法:特判,命中则返回 false
(2) seqs[i] = []: seq 可能为空。办法:indegrees[i] 置为 -1,deq 出现了再置零。若建图后有为 -1 的 indegree ,则返回 false
(3) seqs[i] 长度为 1,办法:seq[0] 单独判断,若 indegrees[seq[0]] == -1 则置零,用于标记 seq[0] 这个点出现过
(4) seqs[i] 可能为 [[2,3],[-4],[6,1e9]],办法:对输入数字的范围做判断

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
if(seqs.empty()) return false;
int n = org.size();
vector<vector<int> > g(n + 1);
vector<int> indegrees(n + 1, -1);
for(const vector<int> &seq: seqs)
{
if(seq.empty()) continue;
int n_seq = seq.size();
if(seq[0] <= 0 || seq[0] > n)
return false;
if(indegrees[seq[0]] == -1)
indegrees[seq[0]] = 0;
if(n_seq == 1) continue;
for(int i = 1; i < n_seq; ++i)
{
if(seq[i] <= 0 || seq[i] > n)
return false;
g[seq[i - 1]].push_back(seq[i]);
if(indegrees[seq[i]] == -1)
indegrees[seq[i]] = 1;
else
++indegrees[seq[i]];
}
}
queue<int> q;
for(int i = 1; i <= n; ++i)
{
if(indegrees[i] == -1)
return false;
if(indegrees[i] == 0)
q.push(i);
}
if(q.size() != 1) return false;
vector<int> top_sorted;
while(!q.empty())
{
int cur = q.front();
top_sorted.push_back(cur);
q.pop();
for(int son: g[cur])
{
--indegrees[son];
if(indegrees[son] == 0)
q.push(son);
}
if(q.size() > 1) return false;
}
if((int)top_sorted.size() != n)
return false;
for(int i = 0; i < n; ++i)
if(org[i] != top_sorted[i])
return false;
return true;
}
};

Share