444.Sequence Reconstruction

1-Topological Sort

if exist circle

if the order is unique

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        for(List<Integer> seq : seqs){
            for(Integer i : seq){
                indegree.put(i, indegree.getOrDefault(i, 0));
            }
        }
        for(List<Integer> seq : seqs){
            int seqLength = seq.size();
            for(int  i = 1; i < seqLength; i++){
                int pre = seq.get(i - 1);
                int cur = seq.get(i);
                Set<Integer> set = map.getOrDefault(pre, new HashSet<>());
                //In case of Duplicate
                if(!set.contains(cur)){
                    set.add(cur);
                    map.put(pre, set);
                    indegree.put(cur, indegree.get(cur) + 1);
                }
            }
        }
        int cnt = 0;
        boolean ans = true;
        Deque<Integer> queue = new ArrayDeque<>();
        for(Integer key : indegree.keySet()){
            if(indegree.get(key) == 0){
                queue.offer(key);
            }
        }
        while(!queue.isEmpty()){
            int currentQueueSize = queue.size();
            if(currentQueueSize > 1){
                ans = false;
                break;
            }
            int current = queue.poll();
            cnt++;
            if(map.containsKey(current)){
                Set<Integer> set = map.get(current);
                for(Integer next : set){
                    indegree.put(next, indegree.get(next) - 1);
                    if(indegree.get(next) == 0)
                        queue.offer(next);
                }
            }
        }

        //Check if length equal
        if(cnt != org.length)
            ans = false;
        //Check if exist circle
        for(Integer key : indegree.keySet()){
            if(indegree.get(key) > 0){
                ans = false;
                break;
            }
        }
        return ans;
     }
}