Java TS sort


  • 0
    D
    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]);
                        fromnode.addChild(tonode);
                    }
                }
            }
            return graph;
        }
    
        private List<Integer> topologicalsort(Map<Integer, GraphNode> graph) {
            List<Integer> ret = new ArrayList<>();
            Queue<GraphNode> queue = new LinkedList<>();
            for (GraphNode node : graph.values()) {
                if (node.indegree == 0) {
                    if (!enqueue(queue, node)) {
                        return null;
                    }
                }
            }
            while (!queue.isEmpty()) {
                GraphNode node = queue.poll();
                ret.add(node.id);
                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;
            }
            public void addChild(GraphNode child) {
                children.add(child);
                child.indegree++;
            }
        }
    }
    

Log in to reply
 

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