LC 0444 [M] Sequence Reconstruction - ALawliet/algorithms GitHub Wiki
if there is ever more than 1 node in the queue, then there is more than 1 node with 0 indegree that we can process, so since we can process either node path, this is node a unique topological sort/sequence reconstruction and we can return False
in general there can be multiple topological sorts. this problem is asking whether there is only 1 unique one
class Solution(object):
def sequenceReconstruction(self, org, seqs):
"""
:type org: List[int]
:type seqs: List[List[int]]
:rtype: bool
"""
sortedOrder = []
# if len(org) <= 0:
# return False
# a. Initialize the graph
inDegree = {} # count of incoming edges
graph = {} # adjacency list graph
for seq in seqs:
for num in seq:
inDegree[num] = 0
graph[num] = []
# b. Build the graph
for seq in seqs:
for idx in range(0, len(seq) - 1):
parent, child = seq[idx], seq[idx + 1]
graph[parent].append(child)
inDegree[child] += 1
# if we don't have ordering rules for all the numbers we'll not able to uniquely construct the sequence
# if len(inDegree) != len(org):
# return False
# c. Find all sources i.e., all vertices with 0 in-degrees
sources = deque() # Q
for key in inDegree:
if inDegree[key] == 0:
sources.append(key)
# d. For each source, add it to the sortedOrder and subtract one from all of its children's in-degrees
# if a child's in-degree becomes zero, add it to the sources queue
while sources:
if len(sources) > 1:
return False # more than one sources mean, there is more than one way to reconstruct the sequence
# if org[len(sortedOrder)] != sources[0]:
# return False # the next source(or number) is different from the original sequence
vertex = sources.popleft()
sortedOrder.append(vertex)
for child in graph[vertex]: # get the node's children to decrement their in-degrees
inDegree[child] -= 1
if inDegree[child] == 0:
sources.append(child)
# if sortedOrder's size is not equal to original sequence's size, there is no unique way to construct
return len(sortedOrder) == len(org)