[Java] Topological Sort Solution


  • 1
    A

    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;
        }
    }
    

  • 1
    I

    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;
    }

Log in to reply
 

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