Sword finger offer II 115. reconstruction sequence

Original link ： The finger of the sword Offer II 115. Reconstruction sequence

 

solution：

        Topology sorting application

const int N=100010;
int h[N],e[N],ne[N];
int n,m;
int d[N];//d Indicates the penetration of the point 

class Solution {
public:
    int idx = 0;
    void add(int a,int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
        memset(h, -1, sizeof(h));
        memset(e, 0, sizeof(e));
        memset(ne, 0, sizeof(ne));
        memset(d, 0, sizeof(d));
        int n = nums.size();

        for (const auto& s: sequences) {
            for (int i = 1; i < s.size(); ++i) {
                add(s[i - 1], s[i]);
                d[s[i]]++;
            }
        }

        queue<int> que; // The queue used for topological sorting 
        // Set all entries to 0 To join the queue 
        for(int i = 0;i < n;i++) {
            if(!d[nums[i]]) {
                que.push(nums[i]);
            }
        }

        int index = 0;  // Topological sequence sum nums Compare 
        while(!que.empty()) {
            if(que.size() > 1) return false;    // The degree of 0 The number of is greater than 1 return false
            int t = que.front();
            if(t != nums[index++]) return false;
            que.pop();
            for(int i = h[t];i != -1;i = ne[i]) {
                int j = e[i];
                d[j]--;// Delete point t Point of reference j The edge of 
                if(d[j]==0) {
                    que.push(j);
                }// If you order j Your penetration is zero , Just point j The team 
            }
        }
        return true;
    }
};