-
Notifications
You must be signed in to change notification settings - Fork 0
/
sequence reconstruction
36 lines (31 loc) · 1.46 KB
/
sequence reconstruction
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
topological sorting
def sequenceReconstruction(self, org, seqs):
# write your code here
bfs_queue, in_degree_table, adj_list, result = [], dict(), dict(), []
for node in org:
if node not in in_degree_table.keys():
in_degree_table[node] = 0
for seq in seqs:
for idx in range(len(seq)):
if seq[idx] not in in_degree_table.keys() or (idx + 1 < len(seq) and seq[idx+1] not in in_degree_table.keys()):
return False
if seq[idx] not in adj_list.keys():
adj_list[seq[idx]] = set()
if idx + 1 < len(seq) and seq[idx+1] not in adj_list[seq[idx]]:
adj_list[seq[idx]].add(seq[idx+1])
in_degree_table[seq[idx+1]] += 1
for key in in_degree_table.keys():
if in_degree_table[key] == 0 and key in adj_list.keys():
bfs_queue.append(key)
while len(bfs_queue) > 0:
size = len(bfs_queue)
if size > 1:
return False
head_idx = bfs_queue.pop()
result.append(head_idx)
if head_idx in adj_list.keys():
for node in adj_list[head_idx]:
in_degree_table[node] -= 1
if in_degree_table[node] == 0:
bfs_queue.append(node)
return result == org