# [Java] Topological Sort Solution

• Very similar to https://leetcode.com/problems/course-schedule-ii/

``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {

Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> inDegrees = new HashMap<>();
for (int[] seq : seqs) {
if (seq.length == 1) {
if (!inDegrees.containsKey(seq[0])) {
inDegrees.put(seq[0], 0);
}
if (!graph.containsKey(seq[0])) {
graph.put(seq[0], new HashSet<Integer>());
}
}
else {
for (int i = 0; i < seq.length - 1; ++i) {
// Make sure node with 0 inNode is also in this map
if (!inDegrees.containsKey(seq[i])) {
inDegrees.put(seq[i], 0);
}
if (!graph.containsKey(seq[i])) {
graph.put(seq[i], new HashSet<Integer>());
}
if (!inDegrees.containsKey(seq[i + 1])) {
inDegrees.put(seq[i + 1], 0);
}
// Avoid duplicate
// org = [1,2] seqs = [1,2],[1,2]]
if (!graph.get(seq[i]).contains(seq[i + 1])) {
graph.get(seq[i]).add(seq[i + 1]);
inDegrees.put(seq[i + 1], inDegrees.get(seq[i + 1]) + 1);
}
}
}
}
// Avoid some cases
// org = [1] seqs = [[1],[2,3],[3,2]]
if (inDegrees.size() > org.length)
return false;
List<Integer> result = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
for (Integer key : inDegrees.keySet()) {
if (inDegrees.get(key) == 0) {
queue.add(key);
result.add(key);
}
}
if (queue.size() > 1)
return false;
while (!queue.isEmpty()) {
Integer tmp = queue.poll();
Queue<Integer> queueTmp = new ArrayDeque<>();
if (graph.get(tmp) != null) {
for (Integer child : graph.get(tmp)) {
inDegrees.put(child, inDegrees.get(child) - 1);
if (inDegrees.get(child) == 0) {
queueTmp.add(child);
result.add(child);
}
}
}
if (queueTmp.size() > 1)
return false;
queue = queueTmp;
}
if (result.size() != org.length)
return false;
for (int i = 0; i < org.length; ++i) {
if (result.get(i) != org[i])
return false;
}
return true;
}
}
``````

• Great solution! I know it's quite tiring to write the tedious and long code. A little comment. We don't need to store all the number visited, just tracking the index of org should be enough:

``````public boolean sequenceReconstruction(int[] org, int[][] seqs) {
Map<Integer, Integer> incomings = new HashMap();
Map<Integer, Set<Integer>> aList = new HashMap();
for (int [] entry : seqs) {
if (entry == null || entry.length == 0) continue;
if (!incomings.containsKey(entry[0])) incomings.put(entry[0], 0);
if (!aList.containsKey(entry[0])) aList.put(entry[0], new HashSet());
for (int i = 1 ; i < entry.length ; i ++) {

if (!aList.containsKey(entry[i - 1])) aList.put(entry[i - 1], new HashSet());
if (aList.get(entry[i - 1]).contains(entry[i])) continue;
aList.get(entry[i - 1]).add(entry[i]);

if (!incomings.containsKey(entry[i])) incomings.put(entry[i], 0);
incomings.put(entry[i], incomings.get(entry[i]) + 1);
incomings.putIfAbsent(entry[i - 1], 0);
}
}
Queue<Integer> queue = new LinkedList();
List<Integer> list = new ArrayList();

for (int i : incomings.keySet()) {
if (incomings.get(i) == 0) queue.offer(i);
}
if (queue.size() > 1) return false;
int index = 0;
while (!queue.isEmpty() && index < org.length) {
int front = queue.poll();
if (front != org[index]) return false;
index ++;
list.add(front);
Set<Integer> hs = aList.get(front);
if (hs == null) break;
for (Integer i : hs) {
incomings.put(i, incomings.get(i) - 1);
if (incomings.get(i) == 0) queue.offer(i);
}
if (queue.size() > 1) return false;
}
if (index != org.length || !queue.isEmpty()) return false;
for (int i : incomings.keySet()) {
if (incomings.get(i) > 0) return false;
}
return true;
}``````

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