# Brief python solution using topological sort

• The basic is to get topological sort of seqs nodes, if it is unique and equal to org, then true, else False

Following is how to implement in details:

in each step,
if we have more than one node whose incoming nodes count is zero then org is not unique, return False

At last we check if the topological sort contain all nodes in the in seqs and equal to org

``````from collections import defaultdict

class Solution(object):
def sequenceReconstruction(self, org, seqs):
"""
:type org: List[int]
:type seqs: List[List[int]]
:rtype: bool
"""
incoming_nodes = defaultdict(int)
nodes = set()
for arr in seqs:
nodes |= set(arr)
for i in xrange(len(arr)):
if i == 0:
incoming_nodes[arr[i]] += 0
if i < len(arr) - 1:
incoming_nodes[arr[i + 1]] += 1
cur = [k for k in incoming_nodes if incoming_nodes[k] == 0]
res = []
while len(cur) == 1:
cur_node = cur.pop()
res.append(cur_node)
for node in adjacent[cur_node]:
incoming_nodes[node] -= 1
if incoming_nodes[node] == 0:
cur.append(node)
if len(cur) > 1:
return False
return len(res) == len(nodes) and res == org
``````

• ``````if i == 0:
incoming_nodes[arr[i]] += 0
``````

is redundant?

• @Aimar88
It is used to initiate a <k,v> pair in incoming_nodes for arr[i].
Otherwise, cur = [k for k in incoming_nodes if incoming_nodes[k] == 0] this line won't work.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.