Leetcode sword finger offer II 115. reconstruction sequence: diagram topology sorting

【LetMeFly】 The illustration ： The finger of the sword Offer II 115. Reconstruction sequence - A topological sort

Force button topic link ：https://leetcode.cn/problems/ur2n8P/

Please judge the original sequence  org  Whether it can be from the sequence set  seqs  Only in The reconstruction  .

Sequence  org  yes 1 To n Arrangement of integers , among 1 ≤ n ≤ 10⁴. The reconstruction   Refers to the sequence set seqs Build the shortest public supersequence in , namely   seqs  Any sequence in is a subsequence of the shortest sequence .

 

Example 1：

 Input : org = [1,2,3], seqs = [[1,2],[1,3]]
 Output : false
 explain ：[1,2,3]  Not the only sequence that can be reconstructed , because  [1,3,2]  It's also a legal sequence .

Example 2：

 Input : org = [1,2,3], seqs = [[1,2]]
 Output : false
 explain ： The only sequence that can be reconstructed is  [1,2].

Example 3：

 Input : org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
 Output : true
 explain ： Sequence  [1,2], [1,3]  and  [2,3]  Can be uniquely reconstructed into the original sequence  [1,2,3].

Example 4：

 Input : org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
 Output : true

 

Tips ：

• 1 <= n <= 104
• org It's the number. 1 To n An arrangement of
• 1 <= segs[i].length <= 105
• seqs[i][j] yes 32 Bit signed integer

 

Be careful ： This topic and the main station 444  The question is the same ：https://leetcode-cn.com/problems/sequence-reconstruction/

Method 1 ： A topological sort

We analyze according to the example ：

Example 1 ：

nums = [1,2,3], sequences = [[1,2],[1,3]]

In example 1 , We know the permutation [1, 2, 3] Two subsequences of [1, 2] and [1, 3]. This means that ：1 Must appear in 2 And 1 Must appear in 3 In front of .（ Because the relative position of the elements in the subsequence must remain unchanged ）

however 2 and 3 Which is in the front and which is in the back ？ According to the given input [[1,2],[1,3]] Unable to judge .

therefore , Example 1 cannot be uniquely determined “ Supersequence ”

Example 2 ：

nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]

In example 2 , We know the permutation [1, 2, 3] Three subsequences of [1, 2]、[1, 3] and [2, 3]. This means that 1 stay 2 front 、1 stay 3 front 、2 stay 3 front .

Then the above three conditions should be met , There is only one arrangement ：[1, 2, 3]

Therefore, example 2 can be uniquely determined “ Supersequence ”[1, 2, 3]

Realize the idea ：

“1 stay 2 front 、1 stay 3 front ” It's easy for us to think A topological sort .

We can build a graph , The nodes in the figure are nums Every element in . If 1 stay 2 Add one before 1→2 The edge of .

Then the diagram of example 1 will be constructed as ：

from The degree of 0 The node of 1 Start topological sorting , After sorting, we found that there are two nodes left , There is no relative order between them .

The diagram of example 2 will be constructed as ：

from The degree of 0 The node of 1 Start topological sorting , After sorting, only the final node is left 3

Specific implementation method

1. Initially traverse mermaid sequenceDiagrams All elements in , about mermaid sequenceDiagrams Medium [a, b, c], Build a a→b Edge and a b→c The edge of , And put b and c The degree of +1
2. Traverse all nodes , The degree of engagement is 0 Join the team . Constantly take nodes out of the queue , Remove all edges starting from this node , And the depth of the node pointed by the removed edge -1.（ Suppose the slave node a There are two sides to start a→b and a→c, that b and c The degree of -1）
3. Until the queue is empty

Be careful ：

1. During the whole sorting process , At most in the queue 1 Nodes .（ That's because if there are multiple degrees at the same time 0 The node of , It is impossible to judge the relative order between these nodes ）
2. After sorting , The penetration of all nodes must be 0

If the above two conditions are met at the same time , Just go back to true

• Time complexity $O(n+m)$, among $n$ Is the length of the arrangement ,$m$ yes $sequences$ The number of elements in
• Spatial complexity $O(n+m)$

AC Code

C++

class Solution {
    
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
    
        int n = nums.size();
        vector<vector<int>> from(n + 1);
        vector<int> inDegree(n + 1, 0);
        for (vector<int>& v : sequences) {
    
            for (int i = 1; i < v.size(); i++) {
      // v[i - 1] → v[i]
                from[v[i - 1]].push_back(v[i]);
                inDegree[v[i]]++;
            }
        }
        queue<int> zero;
        for (int i = 1; i <= n; i++) {
    
            if (inDegree[i] == 0) {
    
                zero.push(i);
            }
        }
        while (zero.size()) {
    
            if (zero.size() != 1)
                return false;
            int thisFrom = zero.front();
            zero.pop();
            for (int& thisTo : from[thisFrom]) {
    
                inDegree[thisTo]--;
                if (!inDegree[thisTo]) {
    
                    zero.push(thisTo);
                }
            }
        }
        for (int i = 1; i <= n; i++) {
    
            if (inDegree[i])
                return false;
        }
        return true;
    }
};

It's not easy to make pictures , If you like it, just like it before you leave ~

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125945290