剑指 Offer II 115. 重建序列

  • 拓扑排序

    为什么使用拓扑排序？

    这个题涉及到子序列，要根据子序列推出满足包含这些子序列的最短超序列。子序列提供的信息仅为：子序列中包含的元素的先后顺序，如[2,4]仅能说明在原来的超序列中2在4的前面，所以可以用拓扑排序（根据元素的先后关系推出一个序列，满足所有的先后关系）

解法

比较容易想到要用拓扑排序，但拓扑排序的写法可以学学

重点是维护两个vector，分别是

  • vector<int> indegrees(n + 1);

    维护每个结点的入度

  • vector<unordered_set<int>> graph(n + 1);

    保存图信息，即每个结点指向的结点的集合

  • 除此之外，在每次删去入度为0的结点同时更新剩余结点的入度时，使用队列queue来维护结点

在拓扑排序中，不断删去入度为0的结点，并更新维护入度的数组indegrees，再删去入度为0的结点…

  • 代码：

    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
    class Solution {
    public:
        bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
            int n = nums.size();
            vector<int> indegrees(n + 1);
            vector<unordered_set<int>> graph(n + 1);
            for (auto &sequence : sequences) {
                for (int i = 1; i < sequence.size(); i++) {
                    int prev = sequence[i - 1], next = sequence[i];
                    if (!graph[prev].count(next)) {
                        graph[prev].emplace(next);
                        indegrees[next]++;
                    }
                }
            }
            queue<int> qu;
            for (int i = 1; i <= n; i++) {
                if (indegrees[i] == 0) {
                    qu.emplace(i);
                }
            }
            while (!qu.empty()) {
                if (qu.size() > 1) {
                    return false;
                }
                int num = qu.front();
                qu.pop();
                for (int next : graph[num]) {
                    indegrees[next]--;
                    if (indegrees[next] == 0) {
                        qu.emplace(next);
                    }
                }
            }
            return true;
        }
    };