Topological order is a valid reconstructed sequence. And if there is no path as reconsructed sequence, then there must be more than one topological order.
class DiGraph:
def __init__(self, size):
self.size = size
self.adj = [set() for _ in range(size)]
def add_edge(self, p, q):
self.adj[p].add(q)
class DFSOrder:
def __init__(self, digraph):
self.visited = [False] * digraph.size
self.postorder = []
for i in range(digraph.size):
if not self.visited[i]:
self.dfs(digraph, i)
def dfs(self, digraph, vertex):
self.visited[vertex] = True
for child in digraph.adj[vertex]:
if not self.visited[child]:
self.dfs(digraph, child)
self.postorder.append(vertex)
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
# convert input to make id in [0, n]
org = [i - 1 for i in org]
for s in seqs:
for i in range(len(s)):
s[i] -= 1
# Check if all points are in the subsequences
inseq = [False] * len(org)
for s in seqs:
for v in s:
if not 0 <= v < len(org):
return False
inseq[v] = True
if not all(inseq):
return False
graph = DiGraph(len(org))
for s in seqs:
for i in range(len(s) - 1):
if s[i + 1] == s[i]:
return False
graph.add_edge(s[i + 1], s[i])
for i in range(len(org) - 1):
if org[i] not in graph.adj[org[i + 1]]:
return False
order = DFSOrder(graph).postorder
return org == order