LeetCode·每日一题·剑指 Offer || 115.重建序列·拓扑排序

链接：https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
拓扑排序
将sequences集合看成一个有向图，题目 -> 判断有向图中是否存在唯一路径
比如sequences = [1,3][1,4][2,3] 当我们选择 1 为这个有向图的人口时，入度为0有3，和 4(就是当选择1作为图的人口时，有3,4两个方向可以选择), 那么此时就出现两条路，不是唯一，返回false即可，题目要求在有向图中遍历时始终只有一个方向，即始终保持整个有向图入度为0的元素唯一存在。
具体实现
很显然这里需要用到拓扑排序，定义数组ans初始化为0，将sequences中所有元素的入度进行统计并记录在ans中，整个图的大小为numsSize，所有ans大小也为numsSize+1，当有向图sequences中不存在nums中的一些元素时，可以理解为有向图会有多个入口，肯定会不满足要求。

代码

bool sequenceReconstruction(int* nums, int numsSize, int** sequences, int sequencesSize, int* sequencesColSize){
    int ans[numsSize+1];//初始化入度
    int queue[2];//记录度为0的元素，因为题目要求始终保持1个，所有不需要很大
    memset(ans, 0, sizeof(int) * (numsSize+1));
    for(int i = 0; i < sequencesSize; i++)//计算所有入度情况
    {
        for(int j = 1; j < sequencesColSize[i]; j++)
        {
            ans[sequences[i][j]]++;
        }
    }
    int node = 0;
    for(int i = 1; i <= numsSize; i++)//寻找度为0的元素
    {
        if(ans[i] == 0)
        {
            queue[node++] = i;
            if(node == 2)//度为0的情况有两个了，不满足要求
            {
                return false;
            }
        }
    }
    while(node)//只要存在度为0的情况，就一直循环
    {
        node = 0;//重新将度为0的入队
        int mm = queue[0];
        for(int i = 0; i < sequencesSize; i++)
        {
            for(int j = 0; j < sequencesColSize[i] - 1; j++)
            {
                if(sequences[i][j] == mm)//将mm指向的下一个元素度减1，因为sequences[i][j]已经被处理了
                {
                    ans[sequences[i][j+1]]--;
                    if(ans[sequences[i][j+1]] == 0)//度为0就入队列，等着被处理
                    {
                        queue[node++] = ans[sequences[i][j+1]];
                        if(node == 2)
                        {
                            return false;
                        }
                    }   
                }
            }
        }
    }
    return true;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度