1、思路

• 可以将sequences中每个序列的每个数字看成图中的一个节点，两个相邻数字之间有一条从前面数字指向后面数字的边，据此构建有向图；

• 题目要求最短超序列是否唯一，问题可以转变成判断一个有向图的拓扑排序是否唯一；

• 在进行拓扑排序时，每个循环都要判断当前队列中是否只有一个入度为0的数字，若否，则表示该有向图的拓扑排序不唯一。

2、代码

class Solution {
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
        unordered_map<int, unordered_set<int>> graph;
        unordered_map<int, int> inDegrees;

        for (vector<int> &sequence : sequences)
        {
            for (int &num : sequence)
            {
                if (inDegrees.find(num) == inDegrees.end())
                {
                    inDegrees[num] = 0;         //初始化入度
                }
            }

            for (int i = 0; i < sequence.size() - 1; ++ i)
            {
                int num1 = sequence[i];
                int num2 = sequence[i + 1];

                if (graph[num1].find(num2) == graph[num1].end())
                {
                    graph[num1].insert(num2);   //建图
                    inDegrees[num2] ++ ;        //累加入度
                }
            }
        }

        //将入度为 0 的数字放入队列中
        queue<int> q;
        for (pair<int, int> inDegree : inDegrees)
        {
            if (inDegree.second == 0)
            {
                q.push(inDegree.first);
            }
        }

        //拓扑排序
        vector<int> res;
        while (q.size() == 1)
        {
            int num = q.front();
            q.pop();
            res.push_back(num);

            for (int next : graph[num])
            {
                inDegrees[next] -- ;

                if (inDegrees[next] == 0)
                {
                    q.push(next);
                }
            }
        }

        return res == nums;                 //判断最短超序列是否唯一
    }
};