# Java TS sort

• ``````public class Solution {
public boolean sequenceReconstruction(int[] org, int[][] seqs) {
List<Integer> ts = topologicalsort(setupGraph(seqs));
if (ts == null && org == null) {
return true;
} else if (ts == null || org == null) {
return false;
} else if (ts.size() != org.length) {
return false;
} else {
for (int i = 0; i < org.length; i++) {
if (ts.get(i) != org[i]) {
return false;
}
}
return true;
}
}

private Map<Integer, GraphNode> setupGraph(int[][] seqs) {
Map<Integer, GraphNode> graph = new HashMap<>();
if (seqs == null) {
return graph;
}
for (int[] seq : seqs) {
for (int i = 0; i < seq.length; i++) {
GraphNode fromnode = getNode(graph, seq[i]);
if (i < seq.length - 1) {
GraphNode tonode = getNode(graph, seq[i + 1]);
}
}
}
return graph;
}

private List<Integer> topologicalsort(Map<Integer, GraphNode> graph) {
List<Integer> ret = new ArrayList<>();
for (GraphNode node : graph.values()) {
if (node.indegree == 0) {
if (!enqueue(queue, node)) {
return null;
}
}
}
while (!queue.isEmpty()) {
GraphNode node = queue.poll();
for (GraphNode child : node.children) {
child.indegree--;
if (child.indegree == 0) {
if (!enqueue(queue, child)) {
return null;
}
}
}
}
return ret.size() == graph.size() ? ret : null;
}

private boolean enqueue(Queue<GraphNode> queue, GraphNode node) {
queue.offer(node);
return queue.size() == 1;
}

private GraphNode getNode(Map<Integer, GraphNode> graph, int id) {
if (!graph.containsKey(id)) {
graph.put(id, new GraphNode(id));
}
return graph.get(id);
}

class GraphNode {
int id;
int indegree;
List<GraphNode> children = new ArrayList<>();
public GraphNode(int id) {
this.id = id;
}