剑指 Offer II 115. 重建序列

原题链接：剑指 Offer II 115. 重建序列

 

solution：

        拓扑排序应用

const int N=100010;
int h[N],e[N],ne[N];
int n,m;
int d[N];//d表示点的入度

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; //拓扑排序使用的队列
        //将所有入度为0的点加入队列
        for(int i = 0;i < n;i++) {
            if(!d[nums[i]]) {
                que.push(nums[i]);
            }
        }

        int index = 0;  //拓扑序列和nums进行比较
        while(!que.empty()) {
            if(que.size() > 1) return false;    //入度为0的个数大于1返回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]--;//删除点t指向点j的边
                if(d[j]==0) {
                    que.push(j);
                }//如果点j的入度为零了,就将点j入队
            }
        }
        return true;
    }
};