Leetcode · daily question · sword finger offer | | 115. reconstruction sequence · topological sorting

link ：https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

Example

Ideas

Their thinking
A topological sort
take sequences Set as a directed graph , subject -> Determine whether there is a unique path in the directed graph
such as sequences = [1,3][1,4][2,3] When we choose 1 For the population of this digraph , The degree of 0 Yes 3, and 4( Is to choose 1 As the population of the graph , Yes 3,4 Two directions can be selected ), Then there are two ways , It's not the only one , return false that will do , The problem requires that when traversing a directed graph, there is always only one direction , That is, always keep the degree of penetration of the entire directed graph as 0 The only element of exists .
Concrete realization
Obviously, topological sorting is needed here , Define an array ans Initialize to 0, take sequences The penetration of all elements in are counted and recorded in ans in , The size of the whole graph is numsSize, all ans The size is also numsSize+1, When directed graph sequences Does not exist in the nums Some elements in , It can be understood that a directed graph will have multiple entries , It will definitely not meet the requirements .

Code

bool sequenceReconstruction(int* nums, int numsSize, int** sequences, int sequencesSize, int* sequencesColSize){
    int ans[numsSize+1];// Initialization penetration 
    int queue[2];// The degree of recording is 0 The elements of , Because the topic requires to keep 1 individual , It doesn't need to be big 
    memset(ans, 0, sizeof(int) * (numsSize+1));
    for(int i = 0; i < sequencesSize; i++)// Calculate all in degrees 
    {
        for(int j = 1; j < sequencesColSize[i]; j++)
        {
            ans[sequences[i][j]]++;
        }
    }
    int node = 0;
    for(int i = 1; i <= numsSize; i++)// The search degree is 0 The elements of 
    {
        if(ans[i] == 0)
        {
            queue[node++] = i;
            if(node == 2)// Degree is 0 There are two situations , Not meeting the requirements 
            {
                return false;
            }
        }
    }
    while(node)// As long as the degree of existence is 0 The situation of , It's been circulating 
    {
        node = 0;// Reset the degree to 0 Of the team 
        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)// take mm Points to the next element degree minus 1, because sequences[i][j] It's been dealt with 
                {
                    ans[sequences[i][j+1]]--;
                    if(ans[sequences[i][j+1]] == 0)// Degree is 0 Just line up , Waiting to be dealt with 
                    {
                        queue[node++] = ans[sequences[i][j+1]];
                        if(node == 2)
                        {
                            return false;
                        }
                    }   
                }
            }
        }
    }
    return true;
}

 author ：xun-ge-v
 link ：https://leetcode.cn/problems/ur2n8P/solution/by-xun-ge-v-nayf/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Time and space complexity