算法图算法

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

字数统计: 1.3k字   |   阅读时长: 5分
,

摘要: 建图的各种 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) <= 1e5
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